The well-known places in Akihabara and Nipponbashi like Liberty and Super Potato do have great selections, but their prices are fairly high because they keep up on the value and rarity. Those places are great for physically perusing VGM. It's the oddball shops that tend to have the best deals, but unfortunately many places like that aren't carrying VGM anymore. Places mentioned like Book Off and Hard Off (second-hand shops) would be great but I've never seen a dedicated VGM section at any of them. Most just have a small anime music section with mabye a few FF albums thrown in so don't bother with them.
When you get to Akihabara, one of the first places you'll run into is Gamerz, and they have a fantastic selection of new VGM up on the 3rd or 4th floor. Animate is another good place to get new VGM, which are all over Japan. The Liberty stores are in Akihabara.
Actually, keep an eye out for a store called Medio. It's a game shop but some of them carry VGM. I got some of my best deals at Medio in Okayama.
I've never run into any VGM stores in Kyoto, so don't expect too much there. As for Osaka, Nipponbashi (near Nanba) is the best place to do VGM-searching. They have a Super Potato and there are some other decent stores but their names escape me. I'll try to update you with the names if I find them out.
- Justin Pfeiffer