The benefits of the horse over fancy beasties fall into three main areas: it's easier to get, easier to maintain, and more broadly useful, even in a world where other options are common enough that they won't run into issues on that basis alone. While individual adventurers or heroes with unique use cases might ride a fantasy creature, everyone who is not a one-man army will find that the horse is the ideal, well, workhorse of a mount.
Acquiring your mount
You can't just go to the mount store and buy a mount if you're in caveman times and stores haven't been invented yet. Capturing, taming, domesticating, and breeding animals is a sophisticated technology, and societies figure out how to do it for the horse long before they do it for anything else. So by the time society starts to domesticate something else as a mount, the horse is already in common usage.
After horses have been invented, they are easy to produce: their gestation period is relatively short and they grow up quickly. This is important because while a horse is still an investment, they are easy to find and to convince the current owner to part with.
Keeping your mount
You can stable a horse, and it will stay stabled, not fly away or decide to do something more interesting. As herbivores, they are easy to feed - critical for an army on the move. Horses are comfortable in broadly the same set of conditions that we are. They do not insist on being entertained, and will not mind if the rider tells bad jokes. In the cold, a horse is warm.
Using your mount
Horses are herd animals that are well-behaved in large groups (like an army). Horses are about the right size for a human to jump into the saddle quickly, and not to get hurt too much when they fall off. Horses are comfortable moving at a pace that humans find useful - neither crawling slowly nor shooting forward so quickly that they outpace the rest of the army. Horses can walk for as long as humans can. Finally, horses are heavy - in a cavalry charge, the horse's significant weight is transferred into the blow of the weapon in a way that a giant chicken simply couldn't match.
A horse is not just for riding. Horses will pull a plough or a cart. They are large enough to carry multiple riders. A horse's flank will shield you from sight or low-velocity projectiles. As a last resort, a horse is edible, and its remaining tissues are valuable for various crafts.