I was thinking something about this... for a base storyline and levels.
At least, if it has to be based of Warcraft :P
During Arthas' trip to Ice Crown, he has to dock the boat because of a huge storm that is terrorizing the sea. Undead or not, if all boats break down during the storm, the Lich King has no way of getting his forces. Without any further hesitation, Arthas docks the boats and arrives on an island, waiting for the storm to go a bit down while being angry of being on a little island.
Since the storm isn't showing any kind of sign of becoming weaker, it would perhaps be best to explore the island and perhaps increase his forces. While exploring the island, they eventually find a Human encampent that was by pure coincidence also waiting for the storm to go down.
But knowing that the human forces are perhaps even twice as big as Arthas' forces there is not much the undead force can do, until a demon that looks similar to the demon lord Kil'Jaeden offers his help to Arthas and asks to be left alone on his island in return. Naturally, Arthas accepts it and sends the demon to the humans' camp while the humans start to explore.
Since being on your own as a normal Demon that is able to take control of the enemy units after a moment of time (Mal'Ganis' ability) the demon slowly increases its own power and its own forces while he tries to enter the human camp, though unfortunately, it is locked down with huge walls of a previous temple that was once build there. The only way of entering, is entering the ruins of the Temple first and reach the other side of the Temple to enter the humans' camp.
Level 1.
Optional: Explore the island, look around, level a bit up, take control of forces to dispose of the little camp of the humans in front of the ruined temple.
Main: Destroy the human camp to enter the ruined temple.
Note: Just the introduction and the "Jungle" map.
Level 2.
Optional: Try to take the gold storages of the humans, kill the Paladin.
Main1: Try to keep yourself hidden. When the enemy found you, an alarm will be rang.
Main2: Try to find the other exit of the building.
Note: The "Dungeon" map with multiple puzzles.
Level 3.
Optional: Save captured undead units to bolster your forces
Main: Destroy the base of the enemy
Note: Your standard, "find and destroy" map.
Or anything similar...
Though this is another idea, not Warcraft based.
Zane Winter is a man once named 'The Hurricane' because of his amazing skills. Zane is a thief and not just a thief, but a master thief who always had success until recently. By a little mistake of calculations, Zane messed up his mission and was captured. The prison he has been placed in is something very different from anything he's ever seen before and not just that, but because the people in that prison will surely die, they will be experimented on. Harris Blobson, his cellmate that has been here for already 2 years has been changed dramaticly into a creature that cannot even feel pain anymore. His abomination body is invincible in battle, but is not able to think carefully anymore.
Zane took advantages of this and uses Harris to escape the prison by using him as a shield with the promise that he would try and find a way to turn Harris back into a normal man. With the little bit of intelligence Harris has left, he accepts it and follows Zane, hoping that Zane can keep his promise.
Level 1. (Dungeon)
The prison. Zane and Harris are in a huge underground dungeon where multiple people are locked in and being experimented on. Harris, being the only one who managed to survive this long is clearly reaching his limit and wants revenge as well, therefore, following Zane in the hope that he can be changed back.
Optional Quest: Rescue other thieves for help, kill the chimeras (just experimented people)
Main: Find the exit
Main: Kill the Warden
Level 2. (Jungle)
After finally reaching the exit of the prison, Zane and Harris reach the normal ground only to be find themselves in a complete base of the people who captured them.
Use Zane's thief skills to get away out of the camp or try and fight your way out of it with Harris - which is a lot harder than with Zane.
Optional Zane: Save other prisoners, break down their H.Q.
Main Zane: Find the exit and break down the gate
Optional Harris: Save other prisoners, break down their H.Q., destroy the experiments, kill the commanders
Main Harris: Find the exit and break down the gate
Level 3. (Jungle)
Try to get to the shore. Try and avoid as many traps of the enemy and get to the shore in a short amount of time. When you reached it, try to defend yourself an amount of time with the little supplies you have.
Optional: Save anyone on your way, try to avoid traps so the enemy will trip over their own traps
Main1: Get to the shore
When you reach the shore, several towers and other useful stuff is placed there, but also a boat that has to be made ready for departure.
Main2: Protect the Ship
Main3: Stay alive
Optional: Kill the enemy commander
-Fladian | 
