I think it is safe to say that a common enough idea is that of the very large flightless bird.
Dark Sun's Erdlu/Crodlu. The vintage video game, Joust (although it glided well). Nausica: Valley of the Wind had one as a mount.
Others mounts:
The Dark Crystal: Landstriders, kind of like a horse with 15-20 foot long legs.
Vampire Hunter D: Not so much a creature, but D rode a mechanical horse.
Avatar: The Last Airbender: Aang rides... well... a six legged something or other. Kind of a cross with a platapus and a bison.