Large record stores in NYC, have gone the way to the dinosaur. There are couple of book stores with flimsy CD sections, one that I think still will be there is the large Barnes and Noble north of Union Square, 14th street. It must be on 18th street?
The large J&R record store and all affiliated stores closed some years back.
CDs as someone else mentioned have migrated to the Internet, the selections in online stores will dwarf anything physically available in NYC.
With skyrocketing NYC rents, most record shops cannot break even. There might be some smaller record shops scattered about BUT, their selections will only focus on obscure DJ LPs rather than a comprehensive library as you should expect.
