"Up" and "Wall-E" are both a plot mess, but held on a pedestal because the first 20 minutes of each is fantastic and people somehow buy into the pile of crap that follows.
"Up": the opening scene is a classic for good reason, and the floating house was a wonderful sequence. But once the house lands (ending the first act way too soon) the central conflict is just how to move the house one last mile. Big deal. So they threw in the talking dog for cheap laughs, and then it turns out Carl's childhood idol (the adventurer Muntz) is actually a bad person. Oooh, a surprise villain -- what a twist! :-/
"Wall-E": the dialogue-free opening was amazing. The early stuff with just the robots on the spaceship was great. But... the movie makes a terrible and incorrect statement about human nature: that we all just want to lie around, fat and lazy. Au contraire! If the future were plentiful and no one ever needed to work, that spaceship would look like Logan's Run, not My 600-Lb Life. People wouldn't be melting into their seats. They would be playing tennis all day and fucking all night. And maybe not even playing tennis.
I've said what I needed to say.