I personally love horses, not so much in the early game but there are some beautiful uses.
You already mentioned the pillaging, horses are superb for this not only that they can move onto a tile and pillage the same turn due to there 2 movement but also because you can upgrade them with sentry and extend there view, with that said they also make great fog-busters.
Not all cities will have a spearman in them and there strength is relatively high, I recently had a game where Justinian cracked open a city of mine defended by machine guns using nothing but a stack of cataphracts.
Speaking of which, if you want to get into civ specifics thats where they start to light up a little bit, not that I'm any expert.
Immortals as someone said can be available very early, they get a +50 vs archers and a +100% vs axeman the preferred early rush unit. They are great for fog-busting and anti-barb work as well.
War Chariots, can also be used as an early rush but really what they are good for is decimating axes, they have 5 strength and 100% vs axes, great in MP since a lot of players rush early. They can beat out a Immortal, Axes, and other Chariots. Great Defensive units but also can be used for rushing/pillaging.
Keshik are great for pillaging and raiding, they get a first strike so that helps against attacking with negative odds such as fighting spearman it also can move over terrain at no cost so they are great for moving across large areas of land or attacking through rough terrain, where as a normal unit would be slowed or crippled these units can move with easy and evade any unit of its time, while doing your dirty work behind enemy lines.
Horse Archers upgraded with combat I + shock also equal 8 strength, I think that is worth mentioning. Which you can do with a barracks and stable.
Cataphracts are also another good one, they are 12 str knights..
A Pikeman is 12 str after its 100%, a cataphract with combat I and shock is 16.2 if my math is right, what more needs to be said? It's very unlikely the AI stacks will be promoted with Combat I, II, and Mounted. So you're left with a unit with absolutely no counter.
To make it better Justinian is also Imperialistic which means you get 100% great general xp, it's very easy to be spitting out level 3 cataphracts, even without switching over to vassalge/theocracy.
Cossacks, are cavalry that slaughter other cavalry which make very good counters to the enemy pillaging your territory as well as pillaging yourself.
These are UU but they are powerful horse units non the less.