You raise some good points, for which I don't have the answer. However:
> Walking upright really seems like something you don't need "much of a brain" for. You don't even need to teach a monkey to do it.
You do need much of a brain for it -- not intelligence, but brain; Gould argued that "intelligence" and higher brain functions arose as a side-effect. Keep in mind that AI researchers found out "the easy things are hard and the hard things are easy" (i.e. locomotion and fine-grained motor skills are harder than they seem, while logic games, chess and go are easier than they seem).
From Wikipedia (https://en.wikipedia.org/wiki/Moravec%27s_paradox):
"Moravec's paradox is the observation by artificial intelligence and robotics researchers that, contrary to traditional assumptions, high-level reasoning requires very little computation, but low-level sensorimotor skills require enormous computational resources."
> As stated this doesn't pass the smell test because a long list of animals are able to "stand" and walk upright (cats, primates, bears, what have you...)
None of those walk upright as their primary means of locomotion, nor are they capable of walking exactly like humans do.
> Not to mention kangaroos, birds (who are also capable of things like flight with generally much smaller brains), etc.
Good point. I don't have an answer for this. Guess you'll have to read some Stephen Jay Gould. I recommend his writing, which is fascinating :)