Ok, I KNOW I can't build the Wall-e from the movie, but how about a similar model that is more doable?
Here are my thoughts:
Tracks are the method of choice, mounted on the sides and tall enough to provide clearance. Not going to be able to be retracted.
Head will be either mounted on a rod that turns in the body and a servo that could tilt the head up and down for the optics (to be decided later) and UltraSound sensors.
Arms are not going to be like the movie and not really decided upon yet.
Now, the kicker is going to be the OS and processor. An old Pentium on a motherboard, I have a few laying around that I can cobble a working one (or five) together.
A few adapter cards to provide some DC-DC power - or simply 'alter' a PSU to allow some battery leads inside and connect to some 12v car battery or 2x 6v motorcycle batteries
Also, a card or two to convert the Hard Drive to something more solid, http://www.opussolutions.com/index.php?p=product&id=50 - a CF card! Or if that becomes to complicated, an old 5gb hard drive laying around would give more than enough space for Linux, control program and data.
Mount a few speaker parts into the chassis, connect them to an onboard or one of hte many old sound cards laying around, install festival, flite or another package and you have speech.
Add a camera or the like on the 'head' and set it up with OpenCV to do visual recognition.
Adding a bluetooth module on the head or chassis and by reading the signal strength, he can locate our cell phones or us if we are carrying them, and give us reminders.
Basically, this is going to be a robot to play with in my house with no real purpose for now. That is going to be the next project.