This paper introduces a framework for representing, generating, and then tuning gaits of legged robots. We introduce a convenient parametrization of gait generators as dynamical systems possessing designer specified stable limit cycles over an appropriate torus. This parametrization affords a continuous selection of operation within a coordination design plane, inspired by biology, spanned by axes that determine the mix of “feedforward/feedback” and “centralized/decentralized” control. Tuning the gait generator parameters through repeated physical experiments with our robot hexapod, RHex, determines the appropriate operating point – the mix of feedback and degree of control decentralization – to achieve significantly increased performance relative to the centralized feedforward operating point that has governed its previous behavior. The present preliminary experiments with these new gaits suggest that they may permit for the first time locomotion over extremely rough terrain that is almost as reliable, rapid, and energy efficient as the very fastest or most efficient outcomes centralized feedforward gaits can achieve on level ground.