How long would it take Nature to destroy the evidence of human existence?

Or until the next glacial period, when all of New York will be scraped clean down to the bedrock.

Perhaps. Last time, NYC was about the southern limit - Lawn Guyland represents the terminal moraine (actually, a couple of them IIRC).

Well, it was close enough last time for the glacier to scour rocks in Central Park, so I think it is quite likely it would happen again.

Well, with Global Warming the city will probably be flooded out first (and perhaps buried in sediment) before a new ice age buried it under ice. So…maybe the glaciers would eventually uncover what the seas covered up for those theoretical alien visitors…

-XT