Evil Empire?
What if you borrowed and modified from Feist, and had a race of humanoids, monstrous humanoids or native outsiders that all use some kind of horse-themed mount, the most popular being a half-green dragon pegasi. Now, since for an epic level character, an 8HD half-green dragon pegasus isn't really that fiersome, you may want to create a new creature with stats similar to a pegasus with the template, but have its HD be higher, like 10-15, and maybe be huge in size, so the riders can be large. Kind of borrowing on the visual concept of the Valheru, but altering all of the details.