I worked on a film last year where we needed a abandoned factory location. the way we ended up getting one was going through demolition companies and found a place that was going to be destroyed an a few months. they didn't charge us or anything.

just watch out for the crackheads though.

I just read that Satellite View of Google Maps is extremely useful when you're searching for unique recording places.

I am in NYC as well, and I know of a few good locations like this, mostly on Long Island. I actually did a library a few years ago of just these kinds of sounds, and most of the footage came from spots on the island. Fair warning; They aren't exactly "open to the public" though. ;) Will shoot you an email.

*Almost forgot! http://abandonednyc.com/

Dude, just record yourself in a foley room.

Footsteps on concrete blocks, metallic surfaces etc or just any surface that a warehouse would include and then add an IR reverb of a warehouse and you are good to go.