I commute daily in NYC from Flushing Queens to Red Hook Brooklyn. I just got the Virgin Mobile version of the Galaxy S3 which runs on Sprints LTE.
Here's where I get LTE Service.
The Entire Length of the 7 Train Line in Queens, from Long Island City Until Main Street Flushing.
Northern Boulevard from Queens Plaza to Main Street.
Parts of Whitestone, Queens.
Downtown Brooklyn, Fulton Mall Area and Barclays Center/Atlantic Terminal
Where I don't:
Flushing outside of Downtown
Red Hook, Brooklyn
LTE has been deployed in pretty decent swaths across NYC, but it's still not available everywhere yet. When you get it, the service is amazing, but even when rolling back to 3G it's clear that service has been improved as well with the Network Vision upgrades.
I previously had the Evo 3D running WiMax, and interestingly I did have service in areas I don't with LTE, but traveling around LTE seems to be more consistently available over a wider set of areas. WiMax coverage always seemed to be available over more limited areas, with the radios switching back to 3G very often while traveling around. 4GLTE when you hit it, seems to be dispersed over a greater area of towers... once you switch to 4G it stays with 4G service for a wider area during your travels.