Pololu has posted a tutorial for an easy-to-build hexapod robot. As can be seen in the above video, despite the robot's small size, it can walk forward or backward, turn left or right, and has IR sensors for obstacle avoidance. Paul Grayson of Pololu writes,
I wanted to point you to a new tutorial I posted on building a really simple, low-cost hexapod walker (using the Micro Maestro, of course) I am hoping that the simplicity of the design will appeal to a lot of people who want to take their first "step" beyond differential drive bots.
Not surprisingly, you can get all the parts you'll need at Pololu. It's based on the new Micro Maestro USB servo controller, three sub-micro servos, two Sharp GP2Y0D810Z0F sensors, and a 4.8v battery pack. Add some jumbo paper clips, some hot glue, and you've got a little robot. For complete documentation on construction and programming, see Pololu's full article, titled Simple Hexapod Walker.