Fury is great fun in pve at least, arms has a bleed build meta that is really good but which really isn't something i like (and as you note: it is quite undertuned if you don't work well with the aforementioned bleed build).
The others i've not tried, but i can recommend arcane mage. In PvE it's a little too easy for my taste but by no means bad, but in pvp it really shines with all the tools it has on hand, teleporting all over the place.
Especially in battlegrounds it is insanely fun to go bowling.
i'm also looking at retridin, which is just devastatingly effective and devastation evoker which feels gimpy as hell but has a lot of utility and effectiveness.
BM hunter is great in case you're having a stroke and still want to crank out good numbers, otherwise it somehow manages to feel realy boring and unsatisfying. I think it'd benefit from an increase in damage spikiness, i.e. higher costs and cooldowns for common abilities, but with altered damage to match.
I'm looking into prot paladin too which is usualy great fun.
And i tried yarr rogue in the prepatch and it was technically demanding but great fun with animacharging and all the quite optional mechanics.
I am also considering a foray into warlock's destro specc which seems both really good and really fun if i could just figure out a playstyle i really like.
So for myself:
1. Try to make arms work for me again, either with or without bleedbuild (i really don't want to use fury in pvp, since i like having speccs dedicated to certain contexts; fury being my pve specc allows me to focus)
2. Destro warlock! Gotta get over myself and my lazy love of dotting.
3. Prot paladin, because throwing shields is cool even if cpr. America has long since ceased to be.