Since you're excited about the prospects of an underground video store (which was voted best by Village Voice... as if they're some kind of authority on the matter), I got you more info:
MULTIMEDIA 1.0
The Kim's (or Forbidden Planet or Toy Tokyo) of gaming, MULTIMEDIA 1.0 carries cartridges for the Commodore 64 on up through Nintendo 64, plus nerd-punk zines, old hardware, and, of course, the latest and greatest discs. It's the only game in town! -Nick Catucci
18 St. Marks Place, Manhattan 212-539-1039 (yeah, I was wrong about it being on Houston Street... oh well)