One of the grad students here that I've worked with used to compete in RoboCup soccer -- programming Sony Aibo dogs to play soccer against one another. It seems that some of the most successful strategies are the more brute force ones. He was describing one hacked dog that, rather than doing animal style locomotion, instead tried to simulate "wheels", which is to say, it kneeled down and did circular motions with its legs. This gave it better control and speed than "normal" locomotion. That's American brute force engineering at its finest.
If you watch those robots closely, you'll see that they're mostly statically balanced, although they are shifting their weight to compensate for the arm motions, and stepping much like real dancers will do. Notably missing from any of those dance moves was anything dynamically unstable, such as jumping, falling into a splits, etc. If they figure out dynamic moves, then it will be time to start bowing to the robot overlords...