Recently boosted this paly and will be playing him a bit over the coming weeks. I dont have a flying mount i like on him tho, most i have are way too small or dont fit a good tauren or paladin theme.
Any suggestions out there? Im thinking of maybe trying to get a protodrake.
Edit: I dont have many mounts and almost 0 from pre legion.
Its a Tauren. There is only 1 answer, and that is Flying Carpet
What about this damn expensive Lightforged Mech?
You know you raise a great point. I really dont care about my profesions on this man so i could just take tailoring for the carpet
I actually went to buy that 2 weeks ago, but its super expensive and wasnt sure id use it. But that was before a pladin, so maybe actually
If you are considering carpet then there are flying kites and disc from Pandaria.
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.
You need a [Ashenvale Chimaera].
It has 2 heads, so you can use one to see where you’re going while the other head can talk you out of spending money on that Mech 
I like the Grand Wyvern (updated version of the old looking Wyvern you buy in Orgrimmar) - https://www.wowhead.com/item=93386/grand-wyvern
You actually get four for the price of one here, because you get the updated Gryphon as well for Alliance. Each of them gets an unarmored and armored version.
The Wyvern scales for Tauren so it doesn’t look tiny while riding it.
proto-drakes the only big ones can handle a tauren
Mounts scale with char so with protodrake you’ll need to zoom out all the way to see something in the background 
What about Ragnaros mount drop? That’s pretty cool.
Something big…
As Saeryn said larger mounts suit Tauren well, I just wish we had more versions of flying mounts. So since we have in game flying pigs, flying rats, flying horses (although mythical Pegasus could give basis for these) why can’t we have Kodo’s that fly? I really like Kodo’s and I think they fit the Tauren so well, I would love a flying version 
Edit: Or mount equipment to change current none flying mounts, to flying mounts.
Eh…your kinda screwed with the whole Tauren(my shaman is one) small mounts on them are the best just for the sake of how suitable they are.Everything else makes them stuck/clip and you cant see it on bigger mounts so they are inconvenient.
Maybe one of the flying moose although I can’t remember how you get any of them
Had no idea this existed, actually really like that. Might look into how long ot takes, cheers!
Problem is all the flying mounts i have are tiny with the exception of the mechagon mount and the throne of thunder pteredax. But i use that for 2 other characters so trying to mix it up a bit
Have you checked out the cloud serpents from Pandaria too? I think there was a quest chain/some farming to get them if I remember, also a few that drop from dungeons/achievements?
I have a few of those (trying to get that rare white one from 8.3). Never actually tried them tho. Will try them later
Not suggesting you go for this achievement, but it does show the mounts available and how to get them.
Helps the vain people like me who always wants a mount to match my mog 
The siltwing albatross.
Trust me.
Someone definitely needs to experiment with strapping some rockets to a Kodo! What could possibly go wrong?