No wonder we can walk around so quickly. 
Weeeell, actually, we did some more poking today, and found that the average speed of travel (at least on Dwilight) is around 15 miles/hour.
According to Wikipedia, the speed of a standard march is approximately 3.5 miles/hour. A double-time march is 1.5x that, for around 5 mph.
It would take a horse at a fast trot to make 15 mph, and I don't think a horse can manage that for 8 hours straight with a noble and all his baggage, or with a couple of soldiers on it.
