All right, my Philly pal gave me some record stores you should probably hit up. I think he skipped over the bits where I asked him about stuff to do, see and/or eat because he has a one track mind: music. Haha! That's all he gave me. I'm sorry.
1) Black Gold - it's in the Carroll Gardens section of Brooklyn. It's also a terrific coffeehouse. The prices are a bit high, but the selection is good, especially for labels like Last Laugh (a punk reissue label based in Brooklyn) that you don't see in many other places.
2) Academy - it used to be in Williamsburg, but they moved north to the Greenpoint neighborhood in Brooklyn (i.e. the neighborhood where Girls is set). I haven't been there since they moved, but they have always had an excellent vinyl selection at mostly reasonable prices.
3) Generation - This is the only store in Manhattan that I'll recommend. It's in the West Village. Everything else there has closed like all of my old spots on St. Marks (even Kim's) but Generation is worth it. I haven't been there in many years, but I know they're still going strong. It's a punk/hardcore oriented store, but they have lots of other stuff, too.