Psychohistory really grinds my gears. No matter how much I try to just think Edward Gibbon! Plot devices! Rule of Cool! it just keeps nagging at me. For instance:
Is there no such thing as free will in Foundation-world? What if one of the later Emperors had decided differently - to keep it all together, to revitalise science, to move stuff off Trantor?
The whole idea of a Seldon Crisis is that the Foundation is put in a situation where there's only one option available to them - in this way they have to follow the optimal course and establish the Second Empire in the shortest amount of time. But every Seldon Crisis we've seen has been resolved by some awesome iconoclast going against what everyone else thinks and pulling some rabbit out of his ass. How does Asimov square that circle? He doesn't want to say 'psychohistory can predict what everyone is going to do' - he says it only works on large groups. So what then - did Seldon predict that Narritivium would step in and sort everything out?
In regards to the free will issue, the suggestion is one of inertia: yes, one of the later Emperors could have decided differently... but how well would he have been able to pull it off (especially 'to revitalise science' - that isn't something you can just decide to)? To make an example, moving stuff of Trantor could have been done... but that could easily be seen as a sign of weakness, inspiring coups that render what that Emperor decided not quite so relevant anymore. As for the second point... well, I can't argue about most of the ones we saw (although, we didn't actually get to see all that many, and the last Crisis we saw had another problem than the one you raise), but at least the First Crisis can be defended to a degree - Salvor Hardin's actions weren't necessary to make the other kingdoms realize what a threat atomic power under Anacreon control would mean, it just speed it up.
For the problem you have with the Seldon Crises, you slightly misunderstand the point Asimov was making. It also helps to know that when he wrote the original trilogy, he was operating by different rules than in his prequels, including that psychohistory worked on individuals to a limited extent. Seldon's plan was never meant to simply predict events, but assured that they would happen the way they did. Each crisis was supposed not only to restrict the Foundation's choices to one if they wanted to survive, but also to breed the next one and the social forces that would compel people to make the right choice then. The fact that we are presented with the events as the results of actions by individuals is a storytelling convenience and nothing more. Seldon didn't predict that Salvor Hardin or Hober Mallow would be the ones to do what they did, just that in those times, the Terminus-controlled religion and ambitious merchants would be the driving force behind the solutions to their respective crises. In fact, The Traders and later The General show that sometimes there wasn't even an individual face to the solution. Linmar Ponyets is ultimately just a cog in the machine that subjugates independent worlds by the force of religion, and the protagonists of The General fail to stop Bel Riose completely, whose threat is eventually ended when his Emperor decides he's gotten too powerful to control for much longer and has him executed.
Psychohistory invalidates itself. It only works when there isn't one man with the power to change the course of the entire galaxy. One man like the Mule... or Hari Seldon himself. If another psychohistorian were looking at the numbers, he'd conclude that the galaxy would fall into chaos for 30,000 years if he weren't looking at the formation of Terminus. Surely Hari himself could have seen that paradox?
Not a paradox by psychohistorical terms. Feedback from psychohistorical methods can be accounted for by the equations. The Terminus element is accounted for and derived from psychohistory. One man like the Mule is not accounted for by psychohistorical methods because it is too small to be be accomodated for. Problem with psychohistory mainly that it cannot account for external non-human factors, like Gaia and the Solarian transhumans.
Psychohistory only works most of the time. It's possible for things to go differently (The Mule and Seldon himself are examples of this). That's one of the reasons the Second Foundation exists: to get things back on track if things do go wrong.
Why are they still human? It would take billions of years to spread across the whole galaxy - why has evolution not occurred?
Evolution requires natural selection. Death and birth rates for humans aren't influenced by external, environmental factors to the extent animals' are.
OK, why haven't they used that technology to live for hundreds of years?
Why haven't modern-day humans used it to? Because external, enviromental factors are not the only factors.
Considering that Asimov's Robots Trilogy are connected in the same universe as the Foundation, they did in pre-Empire times as the Spacers. Humanity has seen how a long life-span can move entire worlds to inertia and lack of scientific cooperation. As scientists start to live longer, they can decide to spend their long lives in a specific matter, and avoid needing constant successors so a new thing can be discovered / invented. It could be also R. Daneel Olivaw saw to that not to happen.
Also, there is FTL travel in the Foundation-verse, so it didn't take billions of years for humanity to colonize the Milky Way at all.