SF Bay Area->South Bay, California:
The Record Man
http://www.recordman.com/
1322 El Camino Real
Redwood City, California 94063
(650) 368-9065
This is a two story house that's been converted to a vinyl vault; every wall of every room (except the bathrooms) are floor-to-ceiling vinyl shelves and additional shelving in the middle of each room, packed with vinyl of all genres, along the occasional but very necessary step ladder in the walk ways. They boast over a million lp's, and I don't doubt their claim one bit. The collection is almost entirely 12" records, with a meager selection of used CD's in half of the front room.
First floor is rock/pop (1.5 rooms worth), metal (1 wall), hard to classify stuff (kraftwerk and such) and other rarities (1 wall), big band (a hall way and another wall), funk, (1.5 walls), jazz (1 room, very nice selection), rap and some other newer stuff in a long corridor in the main room. Second floor is only accessible by request due to its staircase being on the outside of the building and being locked, but it contains nearly as many records as the first: huge array of vocalists (sinatra, nat king cole & such), lounge/exotica/ez listening (les baxter, martin denny, arthur lyman selections are very good), and some entire walls filled with very obscure records from wwii and radio shows and such. There was probably some classical on one of the floors, too, but I didn't notice it. The big artists have entire rows spanning most/all of their catalogs.
Each floor has a dedicated turntable, receiver and pair of floor standing speakers (tucked under windows, since that's about the only space left in the room), so you can listen to any lp you want. Prices are not listed on each lp--you must get a quote from the owner/lackey at the front who looks it up in "American Records" and other such "blue book" type of books, so you know what that means: expect to pay $15-40 per lp, depending on condition (VG+ goes for $15-20, for example). Parking is extremely limited. The vinyl is rather dusty here, and I had to wash my hands after going through a few hundred pieces.
Overall, a nice store to look for those hard to find lp's you desperately need, or to listen to a bunch of old lps you otherwise wouldn't be able to hear otherwise (possibly). Great way to spend an entire day and a boat load of money.
Big Al's Record Barn
522 S Bascom Ave
San Jose, CA 95128
(408) 294-7200
This store specializes in 45's and oldies, where "oldies" is broken down into many sub-genres, (male & female vocalists are separate sections, for example), with a very long wall of rock/pop, a nice selection of soul/funk, jazz/big band, country, and an entire room of soundtracks. Tons of 45's, just tons. Prices look like they were taken directly from one of those "American Records" type blue books, so don't expect to find any crazy deals (a VG record here goes for $20, anything better is upwards of $30-45). However, they do have two racks of $1 vinyl outside the store which had some interesting stuff in it, though mostly junk. The owner (or whoever the old guy is up front) is very nice and willing to help you find something or just chat (and when there's no one to chat with, he usually talks to his parrot... no joke). No CD's here whatsoever.
Plenty of parking, and it's literally 4 or 5 blocks up Bascom from Streetlight Records, which in turn is 6 or 7 blocks up from Rasputins. Very nice little concentration of record stores that sell vinyl.