Kickz - All the shoes that PG gets, w/o the streetwear clothes. [Galleria]
SF2 - Half the store is urban wear and fake diesel/true religion, but they're the only place to find GRDY GNS[almost]. They also usually have legit Bape shoes and most limited Nike releases. [Across the freeway from Greenspoint Mall, by the Subway]
Active Athlete - Notorious for selling shoes early, at least in the old days, and selling samples where available. For a long time they were the premier shoe spot in Houston.[2 location, one on Cullen, one on Fuqua]
The Source - haven't been in a long time, but I hear they get all the SB's and charge retail.[Rice Village, about 2 blocks from PG]
Barney's CO-OP - they get a lot of the inside out AF1s and some dunks. They had their exclusive GRDY GNS shoe, sold out now i believe. Carry Kid Robot and about to start with BBC/Ice Cream.[Galleria]
I dunno what all info the 'shoe guide' posts usually have, but that should help get you started.
I think the full name is "THE SOURCE BOARD SHOP" or something. I'm not too familiar with the names of the streets in the Village[should be by now though], but it's abt a block closer to Kirbythan PG and I think one block over closer towards 59 as well. Personally, I haven't been there in months, but I spoke to somebody who said they get Nike SB releases. They're on Myspace, I think their page has a lot more info.