1. If your want the mounts used by characters to be important they should probably keep up with character Hit Points (usually by having them get free HD as the characters level - equal or slightly less). The alternative is having them level which probably should increase more than just their HP, but then they might become too important.
The default is static mount statistics and replaceable mounts which tap out pretty early in the level progression.
2. The mount needs to be trainable, suited for riding morphologically, and strong enough to bear a rider. It also helps if they aren't carnivores or very aggressive. Particularly warlike humanoids might train beasts that are more dangerous and chaulk trainer deaths to part of life. Bigger races use stronger and bigger mounts.
Horses can cripple or kill but they don't by nature (or after training). And they certainly don't eat you.
3. While HD are based on size and number of HD determines the starting Hit Dice doesn't need to be very high. Most statistics for the real world mounts range from 1 to 3 HD. The only outlier is the Elephant at 8 HD.
The Axe Beak makes a nice Chocobo at 3 HD. Giant Lizards are a personal favorite for adventures (especially the Spider Climbing kind). Giant Goat (Bison and Oxen) and the Rhino (6 HD, where the mount is more dangerous than the rider). Great Cats are a pretty common fantasy mount but the riding position is modified.