Seems like the blokes on foot are going to get there first.
It is a dead easy mistake to make; I did. "Oh, better make sure my infantry leave first because horses are quicker!"
No they are not, they are slower. Trust me. By the time they have checked out every other blade of grass, rested five or six times in the day, complained of being thirsty, and stopped to sniff at that lovely patch of daisies, your horses are going to be well behind.
The cheat is that either you apply magic to get your people around faster or you just hope that no one will notice. The reason is quite a good one; what the hell are they going to talk about for the next month on the road?
But sometimes you want to get it more or less right. So here are some rough guides to help you. Please note, I am not an expert, so this is just what I have grabbed from various places, but it will give you a clue:
Note: I often use leagues and my calculation is 1 league = 3.45 miles = 5.56 km
Wearing just light kit, they can do 6-7 leagues in about seven hours. That is good going!
Fitter soldiers like roman infantry could do 6 leagues in five hours. I assume that was not on hills.
Useful link: http://en.wikipedia.org/wiki/Loaded_march
Remember they will not keep this up indefinitely, day after day, and their dinner will be travelling slower.
The rule of thumb here is that though horses are faster, they have less endurance over distance. So, US Col William Be Hazen apparently said that for the first three days the cavalry will out pace the infantry. On the 4th day, they will be at camp together and from the 7th day, the infantry will be waiting for the cavalry to catch up.
The US Cavalry planned on around 9 or 10 leagues a day though they could increase that by fifty percent on a forced march. However, as noted above, the longer the journey, the slower the horses will get. So if you need to cover a couple of hundred leagues, you might be better doing something like three days at ten leagues then a rest day.
If there are only a handful of you, and you are using pack horses to spread the load, you can probably do better. If you take spare horses, better still. This is all about the weight of a rider; your average hero is not jockey-size and may slow the horse down a lot.
Pony Express riders could cover anything up to nearly 30 leagues in a day, but they changed horses every 4 leagues or so.
Endurance riders can do 30 leagues in a day, but the horse is knackered after that, so it is literally a one trick pony.
Wagon and four
I use wagons a lot. I think it is the romantic in me that likes the idea of ambling along in a nice wagon with the bonnet up and the sun shining down.
If you have a good team of horses and have not overloaded your wagon, then on a long journey, 4 to 8 leagues a day is a sensible range of speed, depending on terrain. You could get more out of them occasionally, but don't do it every day in blazing hot weather or you will end up with horse BBQ.
A small pony and trap can do a fair old pace on a short journey, but is slow on long journeys. Good for popping into market.
Stage coaches in the wild west were really impressive. If they changed teams regularly they could do 30 to 40 leagues in a long day, but that is using a huge amount of organisation and personnel; not just spare teams, but spare drivers and people looking after the stations along the route as well. Someone has to feed and pay for that lot.
These are always destined to mess me up. In a good wind and with the currents in your favour, even your old single sail bucket can do well. The point is that they don't have to stop for either food or rest, but can keep going. fifty leagues a day? No problems. If you need to get down the coast quickly and know a good skipper, go by boat. The drawback can be currents and tides. If your boat's hull allows 4 knots speed and the tide is running at 5 knots in the opposite direction, you are still doing 4 knots, but you are also going backwards at 1 knot relative to the land.
Well, this is fantasy!
Really, they can fly as fast as you like, but here are a few thoughts:
If they are carrying passengers plus luggage, they are going to get tired easily, so will want to rest. If you are flying over an ocean, unless they are crossed with ducks, you may want to plot your route to include the odd island.
On their own, you might want them to take advantage of trade winds. Albatross, when they fly very high, can go ten thousand miles. Basically, they have these huge thin wings, get into the winds and don't flap. This is a good way to get your dragon over long distances, but be aware that the rider will probably suffocate or freeze to death. So solo trips only. Also, their wind shape will make them less efficient than the magnificent albatross.
My rule is that they can fly up to 20 leagues in an hour at high altitude without extra weight. Some species can fly faster, depending on wing shape.
Please remember that they eat so much that taking picnics is probably a non-starter, so they either need to hunt or carry fishing nets - oh, more weight!
Take your time
So there you go, a few random bits of info from Wikipedia, terryburns.net and a few other places I have forgotten about.
If in doubt, make them slower; terrain in frontier style lands is unfriendly, you may need to halve your speed. Plan your map out in a grid of some sort so you do not lose track of where you are. Be realistic about travel times. Remember people have to stop and eat.
It is pointless not taking food if you are in a rush. "Oh, we will travel light, and hunt on the way." Fine, but for every day of walking or riding, you might spend two days foraging and hunting. So, take pack horses and stock up. If your hero is too stupid to plan properly then he/she is a bit short on the hero possibilities too; they will turn up late to the final battle, hungry and knackered.
Remember not just travelling takes time. Hot camps take a bit of setting up. You have to collect wood, light it, wait for half an hour or more before you start cooking and then clear it all up in the morning. Cold camps are faster, but your hero will get tired more quickly because they are cold all the time.
If, like me, you insist on your hero eating beans because they are poor, make sure they soak them and boil them and don't let them ferment or they will get sick. Again, this all takes time.
So, if your are setting your tale in a pre-industrial world and on a nice big continent, then your story may be spread over many, many months simply allow your bronzed Adonis time to get from A to B. That is just how it is unless you go for a lot of wand waving.
Enjoy your trip!