Legs
Legs may look fancy - but they are often only really practical for Anthropomorphic reasons - that is for how they look. They are often a very difficult, and somewhat impractical way to do things.
They do help with complex terrain, but Tri Star Wheels or SHRIMP systems handle this in a much simpler way.
Legs allow robots to crouch, and when using BEAM Techniques you can get some fairly interesting legged robot behaviour without needing a complex controller.
There are many ways to build robot Legs. There are whole books on Leg configurations and gaits.
Gait
The gait is the walking method of the robot. You could visualise it like dancing steps, it shows which leg goes where in a whole walking cycle, or when turning. You must consider this when designing a legged robot, as it may affect the required Degrees Of Freedom for the legs, and how complex the programming or engineering must be. The gait itself affects the potential speed, turning circle, stability, weight carrying potential as well as the energy expenditure of the robot.
Leg Configurations
1 Leg - It is possible to make a hopping robot, although I do not particularly advise it. It would be great for comical value, and building a mechanical zebedee would either entertain, or scare the wits out of children. You would encounter huge problems with stability, and the robot would have to maintain almost constant motion to retain balance, or simply have a very big foot. The foot needs to be able to push down quickly - for a jumping motion, and may need to be spring loaded, or pneumatically fired. The robot would have to be braced well to cope with the shocks it gets from this, and you may require inertial dampening/suspension systems to counteract it.
2 Legs - The Biped is actually fairly complex to do well. You have to really master balance, and moving while balanced. Moving these often involves moving a counterweight above the legs as much as the legs themselves. When you walk, note how you take the weight off of one foot, and put it on to another. I have seen some very simple bipeds, and I have also seen enormously complex ones which require more Degrees Of Freedom in each leg than most of the rest of the robot.
3 Legs - The Tripod may be the most stable static form, but once you remove one Leg, you have a very precariously balanced biped. These may look very interesting - but the gait for these is pretty complex, and requires some well thought out counterbalancing. If you really insist on getting that H G Wells look, then its worth having a go, but I have not seen any successful tripod robots.
4 Legs - The quadruped robot - often in canine form, is fairly common. Depending on how complex and realistic looking you want, you can do these fairly simply with two cams. Since there are many of these forms, quadrupeds probably have the best documented gaits.
6 Legs - Insects by definition have six legs - and it gives you a very stable form, in that you can design a gait that can take 3 legs off the floor at any one time leaving a stable tripod. They are pretty good for complex terrain (depending on the flexibility and control systems) and along with quadrupeds, are also among the most common Legged forms.
Some robots go for 8 or more Legs, and I have indeed seen millipede robots. There are a few uses for these - such as tunnel crawling and similar.
(paid links)