I remember this awesome store in my town called Music Oasis, where you could buy just-released CDs for as low as $9.99. It wasn't an underground store selling bootlegs or anything; it was owned by National Record Mart. But when NRM went bankrupt, this store died also.
My town's mall used to have a Suncoast and Media Play. I especially loved the latter because it had EVERYTHING: CDs, DVDs, video games, books, magazines, whatever. Now, the closest thing to an entertainment-type store is GameStop.