Slingers.

Eaven simpler: slingers seem to - no, wait, they don't seem to, they do - have a longer range than horse archers. And besides: one unit of slingers outnumbers one unit of horse archers + slingers are really cheap (only 65 mnai upkeep per turn with large units), so you can always afford a few units extra of them + they are easily recruited.

This solution also gives your (heavy) infantry some cover to enable them to get at their targets without being nearly destroyed. (Especially in the northern steppes, armies of nearly 20 unit's of Skuda something (horse archers anyway) frequently roam the lands, so heavy infantry would be no good there.)