Behold your savior - Taurotragus, the elands: 
Common elands (T. oryx) come from many parts of southern Africa (a region apparently irrelevant in your alternate world), including the Kalahari, and the 'giant' eland (T. derbianus, however, they're only slightly larger) is native to the savannas, scrublands and sometimes even deserts just south of the Sahel. The dry seasons can get very dry indeed, but that don't worry our antelope buddies none. Unlike camels, they can't directly store water in their body. They are, however, incredibly efficient at conserving water. Their feces is quite dry, their urine is highly concentrated urea, they can change their core body temperature with the weather and they are capable of getting their daily water requirements just from the plants they eat. In short, they'll be happy to lap up some liquid water but in a pinch they really don't need to as much as other animals, especially not horses or cattle.
Camels will make excellent long-distance transport animals or even draft animals. But alas, they're no horses. Yes, it's true that camel 'cavalry' has existed in various forms throughout history. But most of it has been in response to horses because of how much they hate camels. When used like cavalry, camels can be rather unwieldly in wartime situations. They're slower to accelerate, can't keep up their top speed for very long, and their high center of gravity will make sharp turns quite the prospect. It's also less convenient to swipe at people from way up there. Without the deterring, anti-horse quality, they're just big targets.
Both eland species, being antelope of course, are quite athletic, but giant elands are clearly the faster of the two with a top speed of 70 km/h to the common eland's 40. At least two pages from a discount hunting agency and another hunting website claims that they can run continuously for hours, but due to the lack of clarification I'm going to assume at least some of that distance is a half-speed trot. Both species can jump several feet over vertical obstacles.
Both species, while still wild animals, can easily acclimate to human presence. They are bred in captivity, with common eland being the popular choice for farming for meat and milk.
You could probably pick either of these species. For speed, I'm not sure how extensively this has been researched; the data for common elands could come from very few observations, for example. I'd personally go for the giant eland anyway based on what we do know, and though they don't form herds quite as large I don't think it's much of an issue. Size-wise, T. oryx bulls weigh up to 942 kg versus T. derbianus' 1000 kg, which isn't much of a difference and both are quite hefty.
Being ruminants, elands will also be more effective at digesting plant material than horses. They consequently require less food, and elands themselves are capable of both grazing and browsing a wider range of plants than horses or cattle are used to.
Exotic mounts like these can really spice up a world.
(Credit: What If We Had Never Domesticated The Horse?
