Question for the community as I have little class experience outside very few. This questions mostly are related to PVE, as PVP skill is something else entirely.
What do you consider most complex class to play in WoW in general? (Not only rotation, but also utility/mobility in PVE affecting it)
What class is most low complexity but high skill ceiling (easy to play, hard to master)?
Also what class feels most rewarding to play after you learn how to play it well?
Most classes are pretty on par when it comes to difficulty these days, difficulty will most depend on the player and what playstyles they favor and which they have troubles with.
It really depents on what kind of content you do. There are allready big differences in M+ and Raids just for PvE.
What follows next is my opinion and can differ to others. Also I want to mention that while I know how every spec works I didnt played every spec with all tools aviable like legendaries, soulbinds and conduits which ofc can have a huge impact on every spec.
Also I may miss a spec or class but this is what comes to my mind first (its kinda late here)
Classes: Druid, Shaman, Priest
Specs: Elemental, Feral, Shadow (keep in mind that the skill of specs can differ due to different talent builds)
If you just look at utility Druid is probably the king. Especially Boomkin.
I think my spec is probably one of the best examples here: Elemental Shaman.
Its rotation is pretty straight foward. But if you want to do higher DPS you have to play the more complex builds.
Playing with āāElemental Blastāā and āāIce Furyāā make the spec pretty complex due to its micro-management and āāMaster of the Elementsāā. And I love playing it. (Just to explain it: The build is around managing multiple short-CD-attacks that you empower by snapshoting them with Lavaburst(-> Buffs your next spell) )
That being said if you have to play without these talents Ele is boring and easy in ST.
Oh, and lets not forgot that shamans have tons of utility. Which allways increase the skillcap.
But you can allways add druids to the list, since they have tons of utility.
But ofc there are moreā¦ele was just a good example.
Rewarding is due to scaling or tuning.
Here you can see what is rewarding to play in raids.
Here what is rewarding in M+
i have a lot of respect for fire mages.
never understood the need to complex specās/classes the more complex the classes become the less time to enjoy the actual game.
In my opinion the most ācomplexā specs are, feral, WW and survival hunter if you play with WFI talent.
Up until Legion class changes I respected a few specs.
SPriest, Demo Lock, Aff Lock, Fire Mage, Arcane Mage, Rogues, Feral, some others.
These days it kind of feels like a lot of specs play themselves.
I understand that and I must admit I do enjoy PVP way more on specs like Frost DK than I do specs like Enh Shaman / Demo Lock where you have to set up first.
But I kind of feel like Iām playign on easy mode, which I know is dumb, itās just the mind set iāve had for years and years.
On my Enh or Mage I struggle in Arena, swap to my DK and I win way more and I feel good for about 10 mins then Iām like did I actually earn those wins or did I just give up and go easy mode?
Of course Iām not 2100+ CR so I shouldnāt be thinking that way.
Looking for someone that will say Fire mages are the highest skill cap spec ingame.
Waiting patiently 
Demo Warlock is hard.
Most complex, prob Feral in its pre-Legion (ish) state and Demo Lock.
Simplest: DH in BfA, BM hunt, Frost Mage overall but esp the BfA Glacial build and destruction lock
Iām playing feral, elemental and windwalker, I can recommend them for sure. I dab into other specs of these classes too but the highlighted specs are the more complex and imho fun ones. I also get bored when a spec is too easy.
and I was waiting for this comment. also doesnt surprise me its you who made it 
Its you firstly i was waiting for then another two that will hit soon.
In the mean time until the other 2 come back, find a thread to cry about that PI 
cry about what now?
Its literally there 
My number 2 character is a druid. I changed her from feral to balance this expansion and am finding it far more complex than my SPs. Iām trying to find good guides but most of them are either aimed at a complete beginner whoās not got a clue about druids or at mythic raiders.
i think rogue has a pretty high skill ceiling, particularly in dungeons, because thereās so many ways to be creative and useful with your toolkit.
solo interrupting mobs with all ur kicks / gouges / interrupts, learning how to use shroud for different skips and coming up with new ways to use it, learning which mechanics you can cheese with evasion / cloak etc.
i think that alone makes rogue harder than most classes who only really have their one interrupt and the rest is mostly down to minmaxing DPS and pressing binding/treants for their tank occasionally.
Every class is simple - and thatās by Blizzardās design. They wanted classes to be simple to lower the performance gap between āgoodā and ābadā players (to highlight this necessity, look at āthe naked warlockā from MOP).
Thereās not a single spec that is complex on single target. There are 3 classes I would consider complex on AoE - Survival Hunter, Demonology Warlock and Unholy DK. Out of those, Iād say UH is the most rewarding due to the nature of setups/pops.
There sadly isnāt really anything particulary complex from what Iāve played. I think sub rogue is kinda complex since to actualy do something you need very specific setup, other than that I donāt think there is anything in particular complex.
I guess in PvP you can feel more rewarded as a ranged spec, using your CC well but then again ranged classes arenāt hard as far as rotations go either.
Also no all the people who say Demo warlock is complex it isnāt really, itās wastly overstated, apart from it being broken spec there isnāt realy anything hard on soulless generation of shards to put out Hand of Gulādan and Dreadstalkers, occasional Felguard and Vilefind and buff them, not rally.
Seriously mate?
Since when interrupting is high skill cap?
Shroud is high skill cap?
So your godmode immunity does not make the game easy for you (because it does) its actually making it harder?
Nope, its exactly the other way around.
They are absurdly broken with an insane toolkit that makes the top tier which does not make them hard. Actually makes them the exactly opposite of hard as they have all the tools to survive and mobility.