Yeh, that's the problem with legged robots with current technology- expensive and heavy with not enough power.
"Real" bipedal robots have the same problems of multiple expensive motors and balancing sensors as the dog robot. THe sensors have to be more advanced because the balancing problems are worse.
BUt you can make "waddling" bipedal robots. THey use less motors and are more stable so they don't need balancing sensors. Of course, they can't do as much and are much slower. The bipedal is more of a novelty really. This link has examples of waddling robots and you can probably see how they are simpler and different than a "real" bipedal robot.
**broken link removed**
Actually, if you REALLY want to learn and make something impressive, you should try building a two-wheel balancing robot. Like a Segway. It's one step below a "real" bipedal robot except it can usually do a lot more because right now we build better wheels than we do legs. It's also much cheaper and simpler because it has only two motors (one for each wheel) instead of a bunch of motors for each leg. One of these will keep you busy for a while as you try and write the code to get it to balance. You probably don't want to build two of these at a time. Get one working first and build a duplicate then you can have your predator/prey. Cheetah kills the dog when it catches up to the dog and bumps it hard enough to knock it over (in which case you will want them to be light and durable so they don't damage each other).
http://www.geology.smu.edu/~dpa-www/robo/nbot/index.html
THe best part is that for something as as cool as a robot that balances on two wheels, the chance for complete project failure is very low because it's not very different from a simple two-wheeled non-balancing robot. Even if the balancing never works, you can just attach "training wheels" to the robot so it doesn't need to balance (also useful for testing balancing code).
You could add a torso to it...but you probably never will. It's not useful without a sensor head or an arm. It's also trickier to balance becayse you have something on the robot moving around shifting it's weight (especially with the arm, especially if it's hold something). Plus it makes it more prone to damage if it does fall over. It would be best to make the robot expandable to this in the future if you want to do this- you don't want to tackle that before you get a simpler one to balance. This might give you some ideas:
http://www.balbots.com/
Yes, you would need some kind of beacon. It's also possible to buy a hobby vision camera (other cameras are too expensive for most hobbyists) like the CMUCam2 and get it to chase colour instead of a beacon. It means you could also get it to chase a ball and push it around the room.