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.