Kim's Mediapolis (commonly shortened to "Kim's") is a store that rents movies as well as sells and rents movies and music. To sign up, you'll need a checking account. They don't offer membership cards, instead you just show them photo id. Some view the store and its employees as pretentious snobs, but they're generally pretty good about helping you find what you need. Many of their movie sections are organized by director rather than by genre or title.
<googlemap lat="40.805461" lon="-73.964081" type="map" zoom="15"> 40.806071, -73.965187, Kim's Mediapolis </googlemap>