To follow up:
Quick chat with an arborist suggests the tree was worth $3,000-$4,000 based on height and regardless as to its overall health (which wasn't an issue--just came up when I asked about how soon he needed to see the stump to make an assessment), but an in-person inspection would give a better number. The fact that we have pictures of the live tree for height would be helpful.
He referred me to NY Real Property Actions and Proceedings Law, section 861 (like MiddlePart suggested), and suggested I contact my insurance company and see what they thought and see if I have the chance to speak with a lawyer for a quick review of what is involved next. He thought the insurance company might go after the tree company's insurance company for recompense and that maybe we wouldn't have to do much else. He was very kind, didn't want to make the trip here (costing us more $$) before checking other avenues.