How did Hercules travel to all those places in Greece? It must take weeks to go between towns because he goes on foot.
Given that he can out-run a crossbow bolt or a hurled spear and does so many times without being winded throughout the series, and can leap tall mountains in a single bound if his ability to kick people into the air casually is any indication, he's probably got a pretty good clip going on in the overland running department.
The real question is 'how does Iaolaus keep up?'
Olympic Games Herc wants to introduce an ethical alternative to war. He sees two boys arguing, "I'm fastest.", "No, I'm fastest.", so they run a race. Herc inaugurates the Olympics saying "You don't have to kill each other to prove who is the greatest Warrior."
Wrong, Herc, wrong. A race proves the best runner. Shooting at targets proves the best archer. But a Warrior's job is War = killing people. It does what it says on the can.
Well, you can do it without the killing bit. You'd still have to fight (wrestling, for example, jousting), but just don't finish'em off.
Fair enough. Fighting with blunt weapons would indeed prove the best warrior, but the games that Herc set up only proved the best athlete. There is merit and virtue in being the best athlete. My whinge is that Hercules said best "warrior".
Wasn't there a boxing match?
You can add all the different contests up and say that whoever gets the most medals has proven, albeit indirectly, that they're the best warrior. If you can run the fastest, jump the highest and the longest, throw a javelin and discus the farthest, outwrestle your opponents, swim the fastest and so on, you've established your warrior credentials. Nowadays Olypmpic athletes just specialize in one sport instead of trying to win everything, but Herc's working with a much smaller competition and a lot less sports, so the goal of trying to sweep the board and prove you're the best, period, isn't so farfetched.
In Pride comes before a Fall the reason given Iolaus is going to be killed is his pride. Later in the episode Hercules is expressly prevented from helping him fight a HYDRA because if he did it would hurt his ego. It would be different if the God in question wasn't doing her best to help Hercules because she loves him and in the end helps but every time she speaks the core message of what's going on seems to change.
The answer to "Is Hercules immortal or not?" should be very obvious - he's not. The Circle of Fire (third movie) featured the titular fire and its ability to cleanse immortality. Both Hercules and Cheiron spent time in its flames (and the latter is confirmed to have been rendered mortal because of it). As far as this troper is concerned, the big deal made about Hercules's possible (im)mortality from that point on is a Fridge LogicPlot Hole.
I don't think the movies are actually canon though, certainly not any more canon than when we find out that Kevin Sorbo is Hercules pretending to be Kevin Sorbo. Though it's entirely possible that he's like the Norse Gods, ageless but not immortal.