If I remember correctly, from what I read, relay horses allowed the message to arrive faster. Horses get tired too, so after a certain distance the rider would get a fresh horse.
By the way see the Man versus Horse Marathon [1] which proves that horses aren't that fast on long distances, in this particular case 22 miles (35 km).
