I keep hearing mixed reviews of the "new" Horizon Games. From a RPG standpoint, I wasn't too impressed by my last visit there, a few weeks after they re-opened. Their stock looked largely like leftovers from the previous ownership, mixed with a couple of new WoTC releases.
I mainly shop at Nan's because it's the closest to my office. They're pretty good at getting in a range of stuff, but once you get off the D20/White Wolf main thoroughfare, you tend to be at the mercy of whoever did the ordering. If you see something you want that's not from either of those companies, snatch it up. There's no telling when or even if it will ever be restocked. They did a great job of getting the initial WFRP 2e releases, then, when it all sold through, they not only failed to restock the core books, but they seem to have stopped ordering any of the newer releases as well.
One oddity about Nan's is that they never mark down old stock. Which means you can get some stuff there that's long out-of-print and hard to find, if you're willing to do some looking.
Third Planet is really aimed at collectibles. Their gaming stock is small (though not bad and they do actually mark down old stock to move it out). My problem with them is that the place just feels sterile. You get the feeling that the folks who run the place would just as soon be selling...well, anything, really, just as long as they make lots of money off the deal. There's no passion for the merchandise or the cultures that spawned it.
I agree that Midnight Comics is the best shop in town. I just wish they weren't so far out in the boondocks.
Down where I live (Pearland), there's also Montag's, which is a little shop focusing mainly on minis and card games. They have a small RPG section and will special order, but they're not that quick about it. They do host a D&D session or two in the back, but their biggest draw are the nightly CCG and minis events. I buy most of my HeroClix from them, since I play there on Thursdays.
Rice has, as I understand it, a pretty good gaming scene. I went to OwlCon this past year for the first time and was really impressed. It's not huge, but the gaming was good and I was surprised at the turnout. Honestly, I had no idea there were so many gamers in Houston.