First game has orcs and humans in the typical fantasy/gothic setting,
Gothic? The cartoonish aspect was visible even then if you look closely, at briefing screens, unit responses... maybe not as apparent but still. The fact that the cancelled warcraft adventures were supposed to be a cartoon style game should tell you something.
The dungeon crawling missions from the first game to be precise and the fact that the adventures game was canceled could also tell you something.
The Wolf riders in the first game or Necrolytes, Damons, Warlocks, pretty dark and gothic even for 320x200.
the second game adds ogres, trolls, goblins, dwarves and elves.
and dragons, griffins, gnomes, undead, demons and draenei you forgot (though i don't know what else awaits in the exapnsion, as i haven't finished it yet).
BTW ogres are already in WC1.
Draenai weren't in game, manual only and the ogres were only large humans compared to the latter two-headed version. Again nothing exotic like pandas, nagas, murlocks, worgen (furry much?), goblin mechs, owlbears... the list could go on.
Nothing too wacky
goblins and gnomes, with explosives, lightbulbs (electricity!), aircraft; oil platforms, refineries, tanker ships, elven black-powder styled gunships - it was certainly wacky! As well as double headed split-personality ogres.
Holiday themed goblin/dwarven buildings were wacky and the multiple click responses are now a tradition, but nothing wacky about having naval and air units. Elves run the mill, so what's so strange that the smaller faster ship is build by them? Would it be much better if they shot arrows? Not a big counter to a troll ship with canons.
and the story was a series of logical strategic decisions to win a war (in both games).
The manual has many pages of story detailing for example with the events that transpired in the original orcish world resulting in the invasion of azeroth, the demons, the warlocks, draenei, shamanistic roots of orcs, capturing of alexstrasza, the story of the guardian Medivh it's all already there. Some of it was already in the manual for the first Warcraft. And it's not completely excluded from campaigns themselves either, like in for example the mission with Gul'dan raising the isles with Sargeras' tomb, betraying the orcish warchief.
And of course you're forgetting Beyond the Dark Portal expansion.
Yes the set pieces are set early on, but I'm talking about the missions themselves. Like build a foothold in the enemy territory, destroy oil platforms to cripple the enemy fleet, save the elven/troll hero to gain their allegiance.
If Gul'dan revolts your first logical step is to stop him, you can't continue your conquest with a large portion of your army in revolt and that is how it is handled.
I'm not forgetting the expansion pack, while it does introduce heroes as special units it never goes full retard like the spoiled prince seeking his destiny in the north with half the human army in tow.
Mission objectives were still decided by military logic, not some "grand destiny" logic.
Then W3 and TFT came along removing the story from a strategy viewpoint to a more epic fantasy with a hero that has to fulfill his destiny.
Again I remind you of the whole store of Medivh as a Guardian presented as early as in the WC1 manual!
Again you are confusing the game itself with the back story from the manual. I'm talking about how the story was handled in the game via missions and briefings.
They also added so many creature races that they could rival Heroes of Might and Magic with wackiness amped to 11.
I'd say there's still a long way to reach the extreme diversity of races from Might and Magic universe... as well as the fact, that in might and magic you get sci-fi stuff, spaceships and all. (although most of it didn't make it to HoMM series, but it's still canon). Oh, I forget that Draenei came to Azeroth in a spaceship... which is awesome in my opinion.
What could I say to somehing like this? http://gaming.wikia.com/wiki/List_of_Warcraft_miscellaneous_races http://gaming.wikia.com/wiki/List_of_Warcraft_humanoid_races
Those few retcons here and there you call "rewriting"?
All in all I think it's a case of selective memory - it was all there, just not that pronounced becouse of the technical specifications of the era as well as it being an RTS. Being able to actually walk the land forces the producers to fill in the gaps.
You want dark fantasy - look at Warhammer.
Well some of it was there. Deamons for one, but no Night elves. Whole new landmasses were added.
You can say it's more adding than rewriting, but it is interfering with the established stuff, the most logical question being "Where does this stuff come from?".
Now it's a whole new Panda continent after the whole world map was revealed. Many new races in areas that were well explored in previous games.
Funny you mentioned Warhammer. Here's one for you: Did you know Warcraft I was first proposed to Games Workshop as a Warhammer computer game and was turned down?