I've just had an immortal game with Gorgo that employed horseman for a quick science victory. On deity horses become squishy too quickly, so normally, building two armies (archers/warriors) and then (chariots into knights) is a much more reliable strategy.
This time, horses were necessary due to a difficult map that archers could hardly manage and the second pair of horses was nearby.
But the problem is - how to churn out the horses quickly enough for them to be relevant on higher difficulties? Also horses are expensive (-2 gold) so its really hard to maintain maintain an army if you don't get Political Philosophy quickly. And even then, waiting for PP to slot the (-1 maintenance card) may bankrupt you easily (or alternatively, may leave you with no money to purchase a battering ram). And if you try to go for the battering ram in your second city etc, then it may come too late to the battlefield, or you may miss important boosts, or neglect your culture - and then be left with a very late political philosophy and a wounded and soon to be obsolete army.
Strategy as follows:
Start with a builder, into settler (research Mining, Animal husbandry). Improve tiles (boost Horseback Riding, Masonry) / boost Craftmanship. Research 1/2 Archery (wait to kill a barb with a slinger), finish Masonry.
Build 2 slingers (with 50% production card). Get the boost. For civics go straight to Military Tradition (1/2). Move out to Foreign Trade until you clear a barb camp.
Build third slinger up to 1 turn before completion. Then make a builder, also preferably leave at 1 turn before completion. Quickly hit the Archery boost and then start researching Animal husbandry (in the mean time, you can squeeze Pottery/Writing).
Purchase a (2nd) builder. Improve second horses. (Use your second city to hit relevant boosts, e.g. trader etc. monument...) Move builder back to capital. At the exact last turn to Military Tradition get the builder ready to harvest (forest in this case), set production back to slinger (now archer) at (1 turn remaining) - harvest.
Change Military Cards to (50% production for cavalry), set production to Horseman. (Also : use Gorgo's wildcard slot for +2 GG points. Getting this early Classical Great General makes horses relevant up to Turn 90-100 or so on immortal. (Note: if somebody is already going for a GG, either give up on GG points or be ready to closely monitor and purchase)).
Get builder ready for the third chop. Use the overflow to finish the 3rd builder. Use it for 3 extra chops for horseman (in this case 2 stone in capital and overflow from last chop used to speed up a cheap campus district, to boost state workforce). Quickly replace 50% production on Cavalry with -1 maintenance cards. Sell one horses to your 2nd neighbour for lump gold.
You are now at T30-40 and already have a big horseman army that can reach and conquer your first neighbour in a couple of turns. Hopefully you've been nice to them (e.g. sent a delegation etc) so they did not wall up (at least not all cities) etc.
Now the reason I don't normally like this strategy on immortal/deity is time. Its hard to do it in time without a scientific/commercial city state nearby. And I probably would not do it with a civ that has no wildcard slot (for a quick GG), or without hitting either an early Cultural City State or playing a civ that can compensate culture, like Gorgo or Rome etc. Going for an early encampment etc works great on lower difficulties, but is likely to be too late for deity. Hope this helps.