Check out this Make Magazine segment on building mini robots. Then you can move onto huge ones like Big Dog!
John Park builds some lively and inexpensive miniature robots. Starting with a simple vibrabot made from a scrub brush, John assembles a solar junkbot and a slightly more complex beetlebot, which has paper clip 'feelers' attached to switches that allow it to respond to its environment. All it takes are a few common electronic components and some everyday objects and you can make an entertaining robot all your own.