First a little introduction, watch the vide: http://www.youtube.com/watch?v=OJiMUzJHYFk
I started off with the toy titled "Interactive Wall-E". Available at toys'r'us current price $34.99
I am a robot hobbiest and have a lot of expierence with the programming and design to give robots expression and life. The first bit advice I can lend is to be confident. Second advice is to be creative. Together, you're mind will figure out the rest for you :)
There are plenty of peices available to you. My workshop is nothing special. I keep a supply of parts that are low cost. I usually collect items from disassembling other toys :) . Sadly, servos are the most expensive parts of the bunch.
For fasteners I use Zip Ties and an arragement of small screws, bolts and nuts. All are available in cheap combo kits at your local hardware store.
To modify the casings, i use a speed adjustable dremel and sometimes my soldering iron to melt plastic. For dremeling, please keep a vacumn nearby. *Warning: For melting, keep a window open with a fan!!
Also, if you choose to melt plastic peices, use a seperate bit on your soldering iron. The plastic will burn to the tip and make soldering a pain in the butt!
Now for the programming part... This is actually very easy. I do my programming for my robots using the EZ-Robot Project and the EZ-B Robot Controller. It does not require any programming. You can just plug in your servo motors and control the robot from your PC. It also contains voice recognition and a bunch of other neat features. You can get it here: http://www.ez-robot.com
Here's a video of Wall-e in action...
Here's a cute video of Wall-e falling over while chasing his ball :)