I've been struggling to explain why Legion didn't hold my interest and I believe this post nailed it.
One of the things I enjoyed about previous expansions was the quest progression/pacing. For example, questing in WoD wrapped up with an epic confrontation between Thrall and Garrosh. This felt like a satisfying conclusion to everything that occurred in MoP as well as serving as a perfect segue to the larger threat posed by Gul'dan.
Legion, on the other hand, had a disjointed quest structure due to the technical requirement that each zone could be completed in any order. By the time I hit 110 and ventured into Suramar, I didn't feel invested in the story at all. Couple that with story content being gated behind reputation, and I just completely burned out on Legion.
In my opinion, one of the best ways to sustain interest in an MMO is to invest oneself heavily in the lore. When that lore is fragmented and gated behind repetitive content, I quickly lose interest.
Honest question for the two of you: Do you consider the story to simply be the levelling experience? In past expansions it's largely been level level level, virtually no story or you had to really dig into quest text to get it all (Seriously, do you think Grizzly Hills was any more relevant than like, Azsuna for example?), and then a roadblock until maybe the very end where you fight Illidan or Arthas or whatever.
Your example of Garrosh in Warlords - that feels like a culmination to MoP, because it is, but you also had to play ALL of MoP to even know that that was the story. The story of MoP as defined by what you guys are harping on for legion, ends with literally nothing. It would've ended with you saving some Klaxxi paragons or something random. The story in MoP was great, but it took the entire expansion to develop to the point of Garrosh being the bad guy. Nothing in Dread wastes was relevant until then, for instance.
Take that same logic and apply it to Legion, which is both still in progress and you both stopped prior to any current storyline stuff: The story of Legion involves (on a broad level) finding the Pillars of Creation in order to stop Gul'dan and seal the breach in the Tomb of Sargeras. That's what the story was from the beginning, literally the opening quest you do. The four 'random' zones you level through are the places the pillars are held. Your quests through those zones follow straight through to obtain the pillars, and culminate in the dungeons that each zone leads you to in the finale. Finally, after allo f that and the pillars being brought to Dalaran, you find that the Nighthold where Gul'dan is is basically impregnable, lo and behold you find a message from Arcanist Thalyssra asking for mutual help in order to retake Suramar and invade the nighthold. Suramar is then an end-game story progression involving bringing the withered togehter and curing them of their mana addiction, while building an army up to take on Ellisande and Gul'dan inside the Nighthold. You enter the nighthold, defeat Ellisande (helping the nightfallen to become free from the legion in the process) and go fight Gul'dan, where Khadgar uses the pillars (from the 4 zones that you levelled in) to stop the ritual and return Illidan's soul to his body. You then use the same pillars in the Tomb of Sargeras to seal the legion's portal into the tomb, and to tear open a rift and bring Argus and Azeroth basically into orbit of each other, so that next patch we can go to Argus and kill the legion permanently (Since they're in the twisting nether there and will actually die instead of simply being reborn).
I know that's long winded, but my point is, the complaint that somehow the questing zones were random and didn't lead to anything regarding the plot is simply false, and you would know that if you continued on with the story. If you think that it should've led to an endgame right at the end of the questing experience when you hit 110, that's a point of view I suppose, but it's not one that is supported by your other examples (That somehow the questing experience of Warlords led to the end of the storyline from MoP? It certainly didn't end the Warlords storyline). At some point you need to realize that it's an MMO, and the storyline is moving forward much more quickly in the last 3 expansions than it ever used to, and much more coherently, Legion is a part of that, MoP flowed smoothly into Warlords which flowed smoothly into Legion, and presumably Legion will flow smoothly into whatever is next. The leveling experience is basically a search for Macguffins, but that's true of literally every levelling experience that has ever existed in wow - it would both be tiresome and nonsensical to write thousands of quests in order and expect any kind of coherent plot, so instead they write 'hey go to place A, and help the locals with their problems to get Macguffin A'
Again, that's how they've always done it. Yeah, it's nonlinear this time, but it was always nonlinear to a degree. You had choice in Wrath of the Lich king and probably never bothered with half of the zones, and they intended you not to, for example. Same with basically every expansion, they make vastly more content than you need to do. Legion is actually the first time where if you played at launch and levelling without rest or tricks or grinding, you probably did the entire storyline, or almost all of it. So yeah, the order was up to you but you likely saw it all for the first time in wow levelling history.
At this point I'm rambling, I just find this specific complaint bewildering, it's hard to criticize a story you have only seen a small percentage of (and I'm not saying it's great, it's wow it's hokey as it always has been) and then to tout a story that has the exact same structure as a high point for the series.