[link|http://www.extension.umn.edu/distribution/livestocksystems/components/0482-06.html|http://www.extension...ents/0482-06.html]
The trot and pace are equivalent gaits done at about the same speed. The difference is which pair of legs move in sync.
Judging from the comment about horses on hills it looks like the trot lets the horse put out a bit more energy, while the pace is slightly faster.
Cheers,
Ben