Well, technically they can have any animal companion that they can ride. Just needs GM approval.
This is a problem that all classes that get Large companions have. It's just exacerbated by the fact that cavaliers due best with mounted combat, not just with a flank buddy.
You'd be surprised at where a mule can go.
One of the benefits of mules is that mules generally able to work without shoes, whereas a horse is much more limited, especially if it is being ridden frequently.
They've historically been valued for their endurance, surefootedness, and versatility. From the Mule Museum, we read that: "to the north in Asia Minor, the Hittites were the most powerful of the early horse-people–-but they considered the mule to be at least three times more valuable in price than even a good chariot horse."
We can read about their use in ancient Greece: "The mule was highly valued in ancient Greece as well, for use as pack animals and to draw carriages. While boats were used when traveling long distances in ancient Greece, as the country was partially a group of islands, the average citizen rarely left their home area and depended upon the mule as the most common mode of transportation. Mules had much harder hooves than horses and were better suited to cover the rocky terrain found in Greece."
Or on their endurance: "On wagon trains across the plains, mule could cover 30 miles a day, while wagons drawn by horses and oxen could average only five miles a day."
Mules move at a walking pace of about 4-5 miles per hour, while a fast trog can reach as much as 9, and a gallop 20 or more. Trails through places such as the Grand Canyon are done mule-back only. It's theorized that mules owe their strength to their hybridization. From http://h2g2.com/dna/h2g2/A450622: "Mules owe their strength and resilience to the fact that they are hybrids. They are stronger than horses if compared on a size to strength ratio, and they live longer and are less prone to disease. They can also thrive on a diet that is nutritionally poorer than that of a horse. As such, they have proved to be popular pack animals, particularly with the military. During the Second World War, British troops in Burma were almost completely reliant on mules for the transport of supplies."
And for fun, the "Bad-Ass Mule" probably is a true legend. Here's from http://www.lovelongears.com/faq:
Have you seen the "Bad-ass Mule" (one tough mule, mule vs. cougar, mule vs. mountain lion) photos ? (The cat was already shot, the mule simply acted on the carcass.)
Yes, we have seen the photos and have no doubt they are genuine. It is this very typical behaviour, inherited from the donkey's natural dislike of dogs, that makes many donkeys good herd/flock guardians.
Animals are capable of going more places than given credit for. The main issue is usually ceilings of dungeons. As a final quote from the Mule Museum:
Western explorers and trailblazers knew the benefit of choosing a good mule and taking care of it. In choosing a mule, most figured it called for more thought than in choosing a wife. As for taking good care of a mule, which could mean life or death in the unexplored regions, one mountaineer wrote: “live on intimate terms of brother-explorer with your mule”.
Most successful mule breedings are from a horse mother and a donkey father, just due to the number of chromosomes. A stallion who's proven to successfully breed mules can fetch a high price, and would have in olden times. It would be reasonable to expect that in areas with difficult terrain--mountains, few resources, and so on, that the mule is the animal of choice, that effort was made towards breeding ones larger than was typical.
What you might do is just advance a typical mule up to large size, and adjust from there. Let it earn combat training--the things are certainly more fierce than a horse.
Horseshoes of spider climbing. Magic can fix anything.
That's awesome, but I'd have to imagine there was at least some sort of penalty to your Ride check when the animal is going up a sheer surface or upside-down...
What about the Beast Rider cavalier archetype? I haven't played one, but I've been eyeing it--I really want my very own Battle-Cat :)
We have a cavalier in our party, gnome, with a medium size pony. Wildfire is awesome. Good fighter (not the class) and trap springer.