Just bought a book/kit Stiquito for Beginners: An Introduction to Robotics from a local bookstore. Decided it might be a good idea to build a very simple robot before I started construction on my bigger one.
I like the idea of muscle wire (flexinol and nitinol) except it seems to cycle slowly. I've seen parts for sale that use it but the cycle time is usually over a second which seems to slow to build a walking bot with. I also looked at servo's but they are heavy, expensive, and for the weight not very powerful. I keep going back to air muscles but this will require an air pump, bigger battery, and all the stuff to handle pneumatics. This can get expensive and complicated but it seems to be the strongest for the size.
I finally bought what will become the "CPU" for my robot. It's called a mini-box from and is basically a full 800mhz x86 compatible computer running linux that weighs less than 1kg. It meets all the requirements that I needed. I figure spending money on it will motivate me to get working with the rest of the robot. I hope that holds true.