Hi, and welcome to Azeroth!
I understand exactly where you’re coming from. We’ve had many people come to this forum with a similar idea, and I’ve worked with some of them on their plans.
You are currently looking at the Shadowlands route to Wrath of the Lich King. That is the easier and more natural route, and the one you will most likely choose. I have to mention that there is now another, if you want to be completionist and get as near to the original experience as possible.
The Classic Option
Back in the third expansion, 4.0 Cataclysm, Blizzard revamped the Classic ( = Vanilla) questing world. The world suffered earthquakes and floods and general destruction, and they made changes. The continents and the cities and towns and the people are still there, pretty much, but the questing was made a lot faster and more convenient.
The Classic Route: Blizzard has reissued WoW Classic and the first expansion, The Burning Crusade, as they were at the time. These are entirely separate from Shadowlands, There is no connection between them and never will be. They will release the second expansion, Wrath of the Lich King, in about two years. You could start Burning Crusade now, which includes Classic, and level in that and play it for the next two years, and then start as near to the original Wrath as it’s possible to get. It’s along-term commitment, I know, but WoW is a long-term project. If this interests you, ask.
.
The Shadowlands Option
OK, having got that off my conscience, let’s talk about the more straightforward Shadowlands route.
The first thing I have to do is clear up what I think are a couple of misconceptions you have:
As you will find, you will never actually understand what the hell is going on from the game itself. The Warcraft Universe is mostly told in the novels. If you want to get an outline, I recommend starting with Nobbel’s video summarising the whole story
and/or Wowpedia’s Timeline https://wowpedia.fandom.com/wiki/Timeline
Classic has no overarching story. Each zone has its own internal story or stories, mostly about there being a local Big Bad, and as you quest in the zone, you inevitably get all messed up in his business until the two of you meet up and you kill him.
The Burning Crusade does have an overarching story, but it is very disconnected from questing, so you really won’t know it from playing the game. The main characters in the big story of Outland are to be met only in the raids. Like Classic, each zone has its own story.
In Wrath, we still have the zone stories, but the presence of the Lich King connects them all. So you still have the local stories and the local Big Bads, but they are all connected to the Lich King somehow, or working for him, and he himself does appear a few times along the way but dismisses you as beneath his notice. So this theme of getting closer to the Ultimate Big Bad does permeate the expansion.
Actually, after defeating him in ICC, another story develops about the Titans, who ordered the planet, and created the life that evolved into the races of Azeroth. We got hints of those at Un’goro Crater in Classic, but in Wrath we see one of their headquarters, We get to know more about them in later expansions, especially Legion.
As the expansions go on, the devs tie more and more to the main overarching story of the expansion, and make that more and more prominent, to the point where in Shadowlands, I personally feel smothered by it. It’s everywhere. You can’t get away from it. I prefer the times when I was a freelance adventurer following my own path rather than walking through someone else’s dialogue, but I suppose that’s a matter of taste.
So, when you want to know something about the story, look it up on https://wowpedia.fandom.com/wiki/Wowpedia or Nobbel’s channel https://www.youtube.com/user/Nobbel87
There’s a WHOLE lot of quests where you kill wolves or deliver bear asses or pork ribs. I recall the number of quests up to Cataclysm - for either faction - as about 4,000. And more than half have little to do with the story; they’re just about being a murder hobo for the locals in exchange for money and gear.
But doing ALL the quests is a noble goal if you’re a completionist. I;'ve done that myself. There’s a name for it - “Loremaster”. And you can certainly do it. However, the interaction with experience and levels will complicate things.
In Shadowlands, the amount of experience you have to get - that is, the number of things you have to kill and quests you have to do - has been slashed to the ground. In Classic, you damwell EARNED your levels. In Shadowlands, they go by so fast you barely notice them.
What this means is that if you try to do it all on one character, you will find every quest is grey (far below your level) very quickly. Grey quests will be ridiculously easy for you, you will get no satisfaction fighting the baddies, and you will get nothing useful as a reward.
If you want to be a completionist in the game today, I STRONGLY STRONGLY urge you to make multiple characters, called alts, one per expansion. You can choose any expansion to go to once you reach level 10.
Originally, you had to level through each expansion before you did the next. So you had to work your way up to the starting level for each expansion before you could get quests for it. But in Shadowlands, that is no longer the case. Blizzard introduced “Chromie Time”. You meet Chromie, and select any expansion for that character to level in. Then you can level from 10 to 50 in that expansion alone.
So make an alt to go to Outland (Burning Crusade), one for Northrend (Wrath) and so on.
Blizzard have tuned experience so that if you send a level 10 to Outland, and he works through all the Burning Crusade quests, he will be very close to level 50, or more likely he will hit level 50 a little before finishing, so he can finish off as a level 50.
In other words, each expansion now neatly levels one character ready to enter the latest expansion Shadowlands.
So if you’re going to do all of them, make it one character per expansion. It will be just as fast, be a lot more interesting, and you will get to experience the game through the eyes of different races and classes - and at the end, you’ll have lots of characters ready to enter Shadowlands that you can choose from.
I’m going to continue this in a second post.
I came to WoW late in Mists of Pandaria which was I believe the 5th (?) expansion. I felt I had to try to play the game from scratch, or at least explore it as far as possible, to make up for all that I had missed by being so late. So I made a point of leveling my chars entirely by completing all the quests in all the zones of Kalimdor and Eastern Kingdoms. As Gráinne has hinted, this isn’t quite as easy as it sounds, for I had to make sure I wouldn’t get any extra XP by doing dungeons or so, or the zone quests would all go grey for me (denoting trivial for my level). I needed quite some research and detours to make sure I always found a zone fitting for my current level, and I ended up doing it on three different chars. But yeah, it worked, and I arrived in Pandaria with a level 90 char (then the level cap) just in time to participate in a little raiding. 
(there are, or were, in Northrend, which makes sense I suppose but was mighty baffling for a frost mage 
).
