Gecko-style Climbing as a Racial Power?

I am thinking about a Geckomen race for my Barbarian Conqueror King setting. As humanoid geckos, their primary racial ability should be climbing. Real geckos, at least the ones with setae (adhesive toe pads), can climb very well on a very wide variety of surfaces, including glass, and even hang upside down from ceilings.

In game terms, the perfect thing would be to give them permanent Spider Climb, though this might be overpowered (if appropriate). A more balanced option would probably be to give them automatic climbing success on regular surfaces (up to brick walls and craggy cliffs), and a roll similar to a thief’s Climb Walls roll for sheer surfaces (up to and including glass) and ceilings; such surfaces could be traversed at 1/4 speed (regular surfaces at 1/2 speed).

Would this be a balanced racial power? If so, how many Special Powers will it be worth?

I would like to hear the Autarchs’ opinion on this…