Williamsburg is only 5 minutes or so on the L train, get off at Bedford Avenue. It's hipsterville, lots of cool bars, thrift stores and record shops so if you can spare the time and it sounds like your sort of place then I'd recommend a trip over there. There are no record stores in mid manhattan in the touristy areas but you can find some in Greenwich village and maybe the lower East side / East village