I looked into this some more, and I'll share my findings here.
100 Miles Record
In the FEI Endurance Riding Competition senior level, horses travel about 100 miles in one day. The world record for a human going 100 miles was recently achieved by Zach Bitter, who went the distance over a track field in 11:47:21.
The world record for 100 miles by a horse, appears to be set by Yousuf Ahmad Al Beloushi with 11-year-old grey gelding Jayhal Shazal, at 5:45:44. The previous record holder completed the course at 6:21:12, which is approximately the time of several others. I'm not aware of the conditions the race took place, but it may well have been across a desert as many of the FEI Endurance Races are.
Man vs Horse
I have looked into the man vs. horse marathon. I compiled a spreadsheet organized from fastest to slowest time: https://docs.zoho.com/sheet/published.do?rid=20ske6e0ff973f37949dc925b043e33986264
Out of the 34 champion horses and champion humans, the top 24 horses were faster than 32 of the humans. The fastest horse was almost 40 minutes ahead of the fastest human.
Weather has been considered the main factor in the performance of the horses. I'm not sure if the evidences demonstrates that. Llinos Mair Jones on Sly Dai performed the race in 2:07:04 in "Hot" weather, which is still better than 26 of the 34 human champions' times. The weather likely does affect the horses' performance, but it seems to depend largely on the individual dedication and ability of horse and rider.
Having seen some events, I understand the involved horses to mostly be older ones with the riders not being interested in pressing them for victory. Comparing this event to the FEI races, which can go up to 100 miles instead of 22, the horse and rider seemed more reserved (I maybe mistaken). This would explain the gap of 1:11 between the slowest horse (Geoffrey Allen on Lucy (2:31:26)) and the fastest (William Jones on Solitaire (1:20)).
Philippides of Marathon is probably the most famous example of a runner as a messenger, instead of a horse (as well as the famous charge in the battle). It is quite possible he would've been a much better candidate for running the message than any horse the Greeks could have supplied (I would have to leave this to an expert of the field). Philippides is estimated to have run approximately 26 miles in approximately 3 hours, which implies an overall speed of 8.667 MPH, over unknown terrain (which may've lengthened the distance and made the going hard). Philippides also famously died after his run.
While impressive, this famous act does not seem to compete with the feats we know horses can perform, unless we assume the terrain difficulties would greatly impair the horses. It's possible there is a more impressive example of running in history which we are neglecting.
Multiple Day Marathons
Over 100 miles, it seems a horse will win. But what about a longer distance that takes days, or even weeks to cross? There have even been no-sleep marathons where runners keep walking for long periods of time. Could a longer distance and period of time allow a human runner to beat a horse?
Yiannis Kouros ran 473.495 km in a 48 hour period, that's close to 300 miles. A similar feat was accomplished in the 1893 ride to Chicago, where John Berry of Chadron travelled the last 150 miles within a 24 hour period. Notably, riders were allowed two or more horses in that race, but the race did total something close to 1,000 miles over 13 days.
So, in the end? Hard to determine. We'd need a more similar comparison than I can find.
While humans can and have outrun some horses, particularly over distance, it seems that a well picked and trained horse with a good rider consistently wins over human runners in a one-day run of 100 miles or less. It is uncertain if this holds true over multiple day marathons due to lack of a proper comparison, though both contenders perform strongly.