|MadSci Network: Evolution|
First let me say, you are not alone: paleontologists have been searching for the fossilized remains of each of the Last Common Ancestors of the mammalian Orders for decades, and even with recent successes, there are holes that may never be completely filled. It is the unfortunate nature of paleontology that the existance of an organism does not dictate the existance of its fossils: the great majority individuals that die never become fossils.
Horses are members of the Order, Perissodactyla, while humans are members of the Order, Primates. Their relationship to each other can be seen in this Cladogram of the Eutheria at the Tree of Life Website. Both orders are part of the subclass Eutheria, placental mammals, they are also part of the smaller group Epitheria. So, ultimately, the last common ancestor of horses and humans would be a "basal epitherian." Some promising fossils have been reported, but none have been shown to be directly ancestral to primates or ungulates. The best fossils to date, and the prettiest websites, are of much earlier eutherians and later ancestors of each group, primates and ungulates. To see these, check out the following links:
Try the links in the MadSci Library for more information on Evolution.