IIRC there was some testing done on movement speeds ages ago, and it was found that if characters had more than 100 movement points (they start at 80 before traits/ancils) then there was some weirdness with the AI - it doesn't move the full distance etc. I could be misremembering, though. I did increase the base movement from 80 to 100 in my game (descr_characters.txt) and it does feel a bit better though I'm not sure how the AI is reacting to it.

As for fleets, here's a tip/exploit: if you have slow generals or artillery being transported, select the fleet and hit Ctrl+A (to select all the ships in the fleet). You'll notice that the green "field" is significantly wider. Of course, you won't be able to move ships faster than they would be able to go on their own, so it won't help the OP's question, but for annoying things like Olympics then it's good for getting out of a dangerous area quickly.