Here's an idea inspired by a trip to a merry-go-round: who's to say that all the steeds sold by the local ostler are horses? I'm not talking about high-level mounts like griffins and dragons. Maybe 1 out of every, say, 20 riding horses are actually riding goats, rabbits, or the like. The roadways and even the royal cavalry are brightened by the occasional fantastical mount. It makes the D&D world a little more fairy-tale, and what's wrong with that?
There are basically three classes of steed in D&D: riding mounts, war mounts, and exotic mounts (griffins, dragons, pegasus, etc). The last category is already handled adequately by D&D rules. Here are more options for the first two, within the budget of low-level adventurers. Each beast comes with a few variations: alternate animals with the same stats.
UNUSUAL RIDING STEEDS
1 in 20 of every riding horse for sale is actually an unusual riding steed. Roll d12 to determine the type. Unless specified, riding steeds never engage in combat. Price: The same price as a riding horse or pony.
1: Riding rabbit. Travels in a series of jarring hops, up to 10 feet high and 30 feet long. Unskilled riders with a Dexterity score of less than 12 will fall off (double normal damage) after 1-6 minutes of travel. (The rabbit salesman probably didn't mention this.) Variations with the same stats: grasshopper, flea, frog.
2: Riding stag. Will only deign to bear riders of elf size or smaller, and can carry half as much weight as a riding horse. Makes a charge attack that does 1d10 damage. All other combat will be left to the rider. (10% of riding stags are intelligent and speak elven, although the human salesman doesn't know it.) Variations: ram, goat, antelope.
3. Riding butterfly. Hovers between 3 and 5 feet off the ground. Flits randomly in any direction, making general headway in the direction the rider wants to go at 2/3 the speed of a riding horse. Its unpredictability adds a +2 bonus to its rider's AC. Must be pastured on flowery fields instead of grasslands. Variations: bumblebee, hummingbird, moth.
4. Riding palanquin. A floating covered litter that requires no servants to carry it. It flies 3 feet off the ground, carries half the weight of a riding horse, and moves at half the speed. It requires no food or rest, so it can travel as long as its rider extends the occasional pallid hand to point listlessly in the desired direction. Hit point damage must be repaired by a carpenter at 10 GP per HP. Variations: floral throne, broom, hobby horse, blowfish hot air balloon.
5. Riding mole. It can only gallop at 2/3 normal riding horse speed, but it can also dig through earth at 1/10 riding horse speed (alas, not while being ridden). Doesn't mind dungeons and other confined spaces. Variations: earthworm, gopher.
6. Riding ostrich. If it or its rider are attacked in melee, it will respond with a kick or peck, for 2d6, and then run away until the attacker is no longer in sight. Every turn, the rider can try a Dex or Riding check to bring the mount back under control. Variations: kangaroo, flamingo, chicken, peacock, chocobo.
7. Riding bronto. Huge, peaceful herbivore that moves at 1/3 the speed of a riding horse and can carry up to 4x passengers/cargo. Variations: blue ox, turtle.
8. Riding pigeon. Can fly up to 100 feet high unencumbered, or 15 feet high with 100-200 pounds of weight. Variations: other non-raptor bird, bat.
9. Riding squirrel. Can climb at up to half its speed, and can jump up to 15 feet over gaps between branches or buildings. If it sees or hears combat, it will try to climb and escape/hide. Every turn, the rider can try a Dex or Riding check to bring the mount back under control. Variations: spider monkey, jumping gecko.
10. Riding mouse. Doesn't mind entering dungeons and other confined spaces, but fears open fields. Variations: Rat, fox, shrew, chipmunk.
11: Clockwork mount. Roll d20 on this table to determine the type: any result above 10 means it's a clockwork horse. Has the qualities of the original animal but does not require food or rest, and damage must be repaired in a forge at a price of 10 GP per HP.
12: Exotic mule. Roll a d10 twice on this table and combine both animals (or variations thereof) into a hybrid, with the qualities of both animals.
UNUSUAL WAR STEEDS
1 in 20 of every warhorse for sale is actually an unusual war steed. Roll d12 to determine the type. Unless otherwise specified, these animals have the stats of a heavy warhorse and do claw/claw/bite damage equal to the heavy war horse's hoof/hoof/bite. Price: twice the price of a heavy warhorse.
1: War wolf. If a war wolf bites a target, and the unmodified attack roll is greater than the target's Strength score, the wolf pulls the target prone. 5% of these animals talk, but they only say depressing, cynical, or creepy things. Variations: hyena, hound, weasel, badger.
2: War lion. It fights like a heavy warhorse with +1d6 hit dice. For each additional hit die, its price is increased by the cost of a heavy warhorse and the damage of its bite attack increases by +1. Variations: tiger or other great cat
3: War boar. These black pigs often serve witches in black masses. Attack: charge attack that does 2d10 damage, or a gore that does 1d12 damage. Variations: ox, elk, bull, rhino
4: War ogre. An ordinary, poorly trained ogre fitted with a saddle. Has the stats of an ogre instead of a heavy warhorse. If it's subject to any temptation (hit by a new enemy, in sight of meat, etc) it must make a Will/Wisdom check or go out of control. Its rider may force it to ignore that particular temptation by striking the ogre with a whip or other weapon (automatic hit, normal weapon damage). Variations: baboon, bear.
5: War zebracorn. Two-horned zebra, familiar to many from World of Warcraft, but originally appearing (as far as I know) in a Gardner F. Fox pulp novel. The poor man's unicorn. Fights as a heavy warhorse except on the charge, where it does 2d10 damage. Variations: giraffecorn, roostercorn, al-miraj.
6. War frog. A brightly colored poison-dart frog that runs on its back legs. The touch of its skin forces a poison/fort save/Con check or the subject takes 1d6 extra damage. A target may only take this damage once per round, even if hit by multiple attacks. The rider must be heavily clothed and gloved to avoid this poison. The rider may wipe his or her weapons or arrows on the frog's skin to poison them. Variations: Hovering jellyfish (also called war flumph), hovering electric eel (does electricity damage).
7. War wasp. Hovers between 3 and 5 feet off the ground. Makes a single attack for 1d4 damage. On a hit, the target makes a poison/fort save/Con check or takes 1d12 extra damage. The rider should accept that anyone riding a war wasp is probably not one of the good guys. Variations: robber fly, mosquito, also not the good guys.
8. War Beetle. Thick armor gives it a +2 AC. It makes a single pincer attack that does 2d6 damage. On a hit, it can grasp its target and do an automatic 1d6 damage every turn until the target escapes. Variations: ant, beetle, crab, scorpion (a scorpion has a second attack, the same as that of a war wasp, and costs twice as much as other unusual war mounts).
9. War centipede: Makes a single bite attack, which does 1d4 damage. On a hit, the target makes a poison/fort save/Con check or takes 1d6 extra damage. The centipede can carry up to 4 riders. Variation: War cobra.
10. War Wolverine. In addition to its normal attacks, it can release a foul-smelling cloud, straight behind it in a 30-foot-diameter sphere. Anyone in the sphere is stinky for 1 hour. Stinky creatures, and anyone next to them, make all attacks at -1 unless their Constitution is 15 or higher. Variation: polecat, skunk.
11. Flamingo Woman. This sentient tribeswoman has the lower half of a flamingo and the upper half of a woman. She's not for sale; she hires herself out as a steed/mercenary or steed/guide. Variations: centaur, or roll d10 on this chart to determine the lower half of the animal.
12. Exotic War Mule. Roll d10 on this table twice and combine both animals (or variations thereof) into a hybrid, with some or all of the special qualities of both animals. If it has all the qualities of both, its cost is doubled.
Lots of horses rule: You're not going to roll d20 for every horse in a mass cavalry charge. Make the following nonmathematical assumptions: For every 20 steeds, exactly 1 is unusual. Furthermore, for groups of less than 20, if you roll the # of steeds or less on a d20, exactly one is unusual. For instance, for five horses, you'll have one unusual steed if you roll 1-5 on a d20.