how about an extra slider on the world setup that sets the relative abundance of mount tiles? pretty much a copy/paste of the resources slider, but only affecting either the number of wild horses/ wild wargs on the map, or the production rate of the stables/kennels (or both).
"high" setting would be what we have now - virtually no restriction once you have the tech; you'll typically find a horse or warg node within less than 20 tiles of your starting spot; with high setting, mounts are almost guaranteed and generally available
"medium" would be a bit rarer (less than 1 horse or warg node per AI faction, and not in the immediate vicinity of the starting spot; you'd typically get them in the mid game, but you wouldn't have a stockpile of dozens or hundreds already, so you would play with mixed troops for most of the mid game and maybe switch to full mounted armies late in the game
"low" would make them really rare - maybe 2 or 3 nodes total on a medium map; also far away from the starting areas, so you'd have to fight your way through some leveled up lairs and roaming bands of critters to build your stable outpost at some point in the mid/late game; mounted units would be the elite of your armies since you'll only have few and probably not enough to outfit more than a select few elite units
with a slider, players who like it as it is now can just use the high setting, others who are fed up with the overabundance of mounted troops could reduce it and probably eventually settle for the balanced medium setting