From shows I have seen, it would be wherever conditions existed that challenged them to evolve, organize, and be smarter.
This. The cushiest place to live may not have enough selection pressures to move things along.
A lot of things in the human physique are well suited to being a omnivore, who practices at least partial persistence-hunting in hot climates. Some of the most efficient endurance locomotion of any animal on the planet, the ability to sweat and manage heat etc.
So while finding a new fossil find, and a new "oldest" this or that in the family tree of the Hominids will change some parts of the story, I doubt the overall broad plot-lines, that we originated somewhere in Africa is going to change a ton. People don't have a very good grasp of "deep time". Even the paleontologists who dig these things up, most of them probably don't really comprehend it on a gut-level.
When you start dealing in even "small" chunks of geological time, that's more than plenty for any group of humans or proto-humans to get just about anywhere in Africa and Eurasia, just through natural drift of where they were living, not even counting intentional migrations.
