Haven't been back to New York for about 2 years now, so sorry if this is so out of date as to be useless:
Lost and Found out in Brooklyn at Savalas bar was running every Tuesday. Can't find the link to Lost and Found's website, think they had something on Facebook, but here's a review of Big City Records which Jared and Chris who DJ at L&F run. The review comes over very 'breakbeat' (?) orientated, but they do play a lot of really good crossover and have a great range of 45s in the store itself.
Be warned though, typically the venue is a tiny bar, with a room of sorts at the back, still very small, and although people do dance there's limited space, limited seats, and as entrance is often free you are of course expected to be buying drinks as far as the bar owners are concerned.
Seemed like a very varied clientele, some of whom had probably just stumbled by the bar and fancied a drink, others fairly young and clearly into the range of music being played. Rarely got going before 10 at the earliest (although you might miss the DJ playing the best Soul - I caught the end of Honeydripper who played some blinders).
I posted a set of photos of various 2nd hand record shops around the city on Flickr.
Hope you have a great time living over there.