Here's a fun project that simulates walking without the challenge of keeping the robot balanced and upright.
Each leg is identical and is controlled by its own NXT. A leg starts off completely straight and when pivoted forward at the ankle, a touch sensor is activated which triggers a motor to bend the leg back at the knee and another motor to swing the leg forward at the hip. The process is repeated on both legs merely by leaning the robot forward so as to activate the touch sensor on the back ankle.
I was thinking that a possible improvement would be to suspend the walker along a pulley.