The Compleat Strategist
11 East 33rd St.
212-685-3880
It's half a block west of the Empire State Building, which you might be planning to visit anyway. The Strat is by far your best option in NYC. The other reasonably good place to go is Forbidden Planet, which is somewhere around Union Square. They have more comics and toys than gaming goodies, though.
A block or so east of the Strat is Jim Hanley's Universe, which is an excellent comic store that (if memory serves) occasionally has gaming stuff.