You have a few options.
- Bovins [sic, of tribe Bovini]: As Neil said, these could be a good choice, potentially. Though more used to a heavier fighting build than a cursorial one ideal for riding, bovins nonetheless have plenty of stamina themselves and lankier, energetic breeds can definitely form. The importance of cattle rivals that of horses in terms of transport value. They've definitely shown their worth in the ability to carry goods, pull loads and power farm or siege equipment. As for riding, Longhorns are becoming popular riding animals in Texas:
In a combat situation, I'd do away with the horns. A war steer could benefit from some kind of helmet, but horns can get stuck and become lassoed. They're cool, but a liability. Breed them out or poll them.
Being ruminants, they can also more efficiently process their food. Very economical. I think this would be the default.
- Large antelope: Elands, kudus, etc. You can get the 'battle readiness' and ruminant ability of a bovin with the stamina and agility of a horse. Good mix.
Elands and other antelope are often bred in captivity, and elands are even farmed in some places. Quite amenable to taming in real life, though I'm not sure how much leeway we're allowed.
- Large deer: Elk, reindeer, Megaloceros etc. Similar advantages to the bovids above. Something about deer makes them incredibly strong; even whitetail are said by the people who physically caught them to be almost as strong as a horse, though that's anecdotal. Reindeer are nowhere near the size of horses but are capable of carrying riders and pulling sleds at up to 50 mph for great distances.
Though their wild forms are often skittish, they seem to be very quick to acclamate to humans from the amount of deer parks throughout the world, not to mention pet deer. Elk are farmed today.
They also have a different interspecies combat style: whereas bovids charge and back away, deer continually press forward and lock antlers until the other gives up. This can be an advantage or disadvantage depending on what you want, but many combat riders may be using females anyway to limit liability.
- Camelids: Camelids are incredibly valuable transport animals. Their sure-footedness over some crazy terrain and carrying strength actually negates the benefits of the wheel in some places, where old Persian roads began to fall in disrepair after the adoption of the camel. They are insanely adaptable, especially Bactrian camels which are very close to being all-weather animals.
Though camels are immensely strong and efficient travelers, they lag behind ever so slightly on the war front. Camels are slightly slower overall, slower to accelerate and are less agile. Their higher center of gravity won't make for fun turns, and it's less convenient for mowing down ground troops on account of their size. The biggest advantage of the war camel was its negative effect on horses, which is a moot point in this world.
There are probably some smaller camel species, but I only know of two llamas that may fit the bill. Hemiauchenia and Palaeolama reached 400 and 300 kg respectively, and the latter is just under the minimum weight range of ancestral horses but still workable.
- Extinct Giraffids: Unfortunately, the problem with extinct animals is it's very hard to gauge how prolific they may have been or what their social structure was. Extant giraffes take four years to mature and have small, loose herds; okapi have essentially no social structure to speak of but take between 1.5 and 2 years (faster for females) to mature. Both rates are relatively impressive for their size, so we may not need to worry about slow growth rates.
Domestic giraffids would, in my opinion, make a great addition to anyone's world - depending on how hard you want this science, you can probably handwave a herd structure in to make them suitable horse substitutes (though they seem to compete with cattle and camels just as well on their own as draft animals). Most of these went extinct in the Miocene (save for Sivatherium which died out in the late Pleistocene), but that too can be handwaved if the author is willing.
Of these, Helladotherium, Palaeotragus, Samotherium, Shansitherium and Bramatherium have sizes and weights comparable to riding horses (organized from the lightest, 250 kg, to the heaviest, 450 kg for the smaller B. perimense). Paleotragus seems to be the most well-rounded for the 'horse' niche, but any of these could have horse-built breeds when domesticated. The first three are all more or less common throughout the Old World and Bramatherium ranged from Turkey to India, so in this hypothetical timeline where one of them survives there's a chance they may find it into human captivity.
And should you decide to create a world where no transport animals exist, there's always the potential for more exotic alternatives...