Assuming that horses went extinct early in history, what would replace the horse, and how would the change in domesticated animal affect the development of the first civilizations?
Info on horse extinction in Americas (OTL)
Note that this question will be followed up with another one based around extrapolating further human development from the situation in the accepted answer.
Well on one hand, many of the animals which aren't horses that have been domesticated over the years for a similar purpose of transportation would be used far more often. Donkeys would likely be the popular choice because although they are stubborn, they will still take you to where you need to go, and they can also carry quite a bit.
Camels too would be more commonly used as well, especially around areas with water drinking areas far and inbetween.
While elephants would certainly exist, for various reasons they are not practical for general transportation. They would perhaps be better suited for manual labor as they are used today in some countries.
However in war, you are likely not going to see a donkey or a camel being ridden by cavalry, not because it would look silly (that mostly comes from our idea that cavalry ride horses), but rather because horses tend to be very strong and fast runners, which is what you'd look for in a charged attack. Camels may be strong, but they aren't going to want to run fast and donkeys are somewhat low to the ground and so perhaps not ideal for the charge.
So my idea is that you would see bulls used. Yes, you heard correctly. Bulls are notoriously hot-headed, but then they are also not used to being ridden. If you raised one from a calf, treated him properly and gave him proper training, you'd have yourself a very strong and very fast war horse with horns. Consider also that horses have had centuries of domestication. If bulls had been domesticated over centuries, I don't doubt that they would be no more difficult to ride than stallion horses are now (which is to say, difficult, but not impossible).
And while bulls would make a solid pick for charging into battle, if we're going to try to make this interesting, then this is relevant.
You have a few options.
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.
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.
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.
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.
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... 
Some ancient civilizations used elephants like Carthage. If there had not been horses, Carthage would have extended the use of North African Elephants to others areas or countries like the Roman Empire.
Elephants may be only used for war because the maintenance of one of them would be very expensive for a regular farmer. In medieval age, they may have easily ground up hundred of soldiers. And after the discovery of gunpowder, elephants may have a carried cannons on their backs.
More information here
As a personal mount, Camel seems a good choice.
Maybe people would simply focus more on running as in ancient Greece. As a reminder, they were using runners as courier because, on long distance and uneven ground, men are faster than horses.
On more leveled ground, you could imagine that bicycles or scooters were invented earlier. After all, if you ignore snobism, a scooter is a rather efficient thing.
As an animal to tow a car, it would be big dogs, bulls or elephants (from the more docile to the wilder). Or men.
If you want to focus on the surprising substitution, Elephants, Camel or giant kites are good ideas. But the reality as analysed by an economist would simply be that human have to work more.
SHEEP, not necessarily a baaaad option.
Yes, a large domestic sheep can carry a person. I had the unenviable task of firmly gripping a sheep's collar while straddling it just behind the front legs.
Another person was giving vaccinations further aft. The ram was the largest. My feet barely touched the ground. He was quite docile, since he'd been raised in a petting zoo. Evidently, he didn't like the injection and I was taken for a sheep ride. Thankfully he gave up after about 10 meters.
Start with a bigger varity of sheep, put in a few dozen generations of selective breeding, and then we'll all be able to join the sheep cavalry. :-)
