I’m very happy with my Elemental…he doesn’t like Pallies though…
In the end, Tauren are a bit screwed on decent mounts, however Dragon, Drake or protodragon are less awkward.
Theres the red flying disc, from the lorewalkers.
And Lorewise there’s the Wyvern, Wyvern are revered creatures in Tauren lore, if I recall correctly.
I use the Battlelord mount on my Warrior.
The wolfhawk on my Hunter, wich I also find fitting…but ofcourse none of those help you with your Paladin.