Granite Run Mall in Media, PA has Showcase Comics which is effectively a game store. It has been a long time since I have been there (it's about twice my "drop by" distance), but it apparently is still there.They were very common on the east coast too, BITD. Legends is still in the Vallco mall in Cupertino (South Bay), but that's the only one I know of, offhand (the GW store in the Cherry Hill, NJ, mall closed up, apparently---or at least it's not listed on their site).
There's no shame in attending the Mall of America. It has the aforementioned Games By James, as well as an excellent Lego store and, well, all those rollercoasters and rides.
(Games By James is great, but given the current economy, I guess I shouldn't be too surprised that while there were recently 10 Games By James stores, there are now only 7: http://www.gamesbyjames.com/about.htm)