You start out on a small island with a nice and simple outlook: simply take the available town and start building it, and clear the island of resources, visiting boosters and flagging mines. When you have done that, there is a Shipyard on the southern shore. Be careful, though; there are Red heroes on the waters, who will attack you if you get too close, so bring a decent army if you are going sailing. Also, make sure you leave some good defences at home in case the enemy comes knocking (for me, they came at the beginning of week 4). Fortify your town and leave Malwen with a good army (or make sure you have Town Portal ready).
Once your town is attacked, use spells and ranged attacks to weaken the enemy army as much as possible. Focus on the troggies since they can dig under your walls. If your town is fortified, you should win.
Vayaron needs to cross the bridge into the southeast to reach his second quest. Bring a decent army and make your way across (clearing the area on your way, visiting all buildings, including the Altar of Shalassa). Once on the other side, head north and flag the Gold Mine. Heading south on the eastern bank, you will find more boosters and a gate to the east, which is closed by a Seal of Malassa. Even further south is a Mysterious Crypt and a Dragon Utopia, but you aren't ready for those yet, so this is a good time to go back and collect reinforcements.
If you take a boat from your starting town and sail straight south, you will reach a Whirlpool which allows you to reach a southern land area, upon which there is a Fort. Bring a big army, as there are several roaming enemies around on the water; they come from a town further east. Take the fort when you can, and rebuild it so you gain control of the buildings in the area. There is a staircase here, but you don't have to go up there yet. There is a Dwelling which you should flag too. Afterwards, clear the area and get back on the ocean.
Head east to fight the Red player's armies and main town. After defeating the first two armies, you should be able to take these guys with little difficulty. Do it quickly, so they won't have time to rebuild and come back and harass you. Once the town and surrounding area is under your control, use Malwen to go up the stairs just to the south of your new town. Make sure you bring a big army.
Upstairs, you will see a two-way portal and a path to a Yellow fort, protected by a Seal of Shalassa. You should be able to open that since you visited the corresponding altar when you first crossed the bridge to the small island earlier. Take and rebuild the fort, and as soon as you can, visit the Altar of Malasssa just east of it so that Vayaron can travel across the bridges once again and break through to the eastern area of the map downstairs. Beware that once you take the fort upstairs, Yellow player may attack you any second. If you hide in the fort, he may bypass you and go for your southern town and fort. I lost both southern strongholds like that, but it was a pyrrhic victory for Yellow as the amount of troops dwindled after attacking my fortified places. It was a nuisance more than anything else, having to wait for her to finish attacking everywhere. Soon after, my main armies intercepted the hero and took care of her, reconquering the lost town and fort shortly after. Then I sent Malwen to conquer the upstairs. She should take a right, go through the garrison, continue north and capture the town there, and then clear the area around it. There may be some remaining Yellow heroes, but no big challenge. Sending for backup via caravans is a good idea, though.
(By the way, here's a neat trick for easing the use of caravans at this stage in the game. You will notice that in order for you to send caravans from your home town, you need ships in the north. This will cause an accumulation of ships on the southeastern shore, while there are none to the north where you need them. What you can do is move a hero over land across the bridges to the eastern shore and go as far south as possible, then use Town Portal. Since it takes you to the closest town, you should be teleported to the south. Then you can travel north by boat. Rinse and repeat until you have lots of boats by a shore your caravans can get to.)
Anyway, back to our main quests. While Malwen wreaks havoc upstairs, now is a good time to send Vayaron to visit the invisible (yeah, right) library to the east. Since Malwen visited the altar up there, the seal can be broken. Visit the place and after the cutscene, clear the area. Make sure you visit the Altar of Ylath nearby. After that, I recommend using Vayaron for the afore-mentioned caravan trick for a while, while Malwen clears the area upstairs.
When the upstairs town is taken and the area around it secure, go north through the garrison and keep going north (don't turn right to finish the banshee quest yet). To the north is another area (oooh, shiny!) with lots of goodies, including an Altar of Elrath. Visit it and then head back south to the fork in the road south of your town; the left path leads up to a seal which you can now open. Going through it leads to another area with a passage back into the underground. You are now on the centre island, with an Elite dwelling on it, which is nice, but also the Altar of Sylanna. Clear the whole island, including capturing the town to the southwest, before moving on.
When Malwen has a big army and nothing else to do, visit the banshee north of the upstairs town. This means a battle against a lot of ghosts, so be prepared. With that done, there's the next mission (assuming you have killed off the roaming heroes already), and that's a prison break. Look at the upstairs map, southwestern section; that's where you need to go. Head to the southwestern island in the underground and find the stairs located there. Head up and there you are. Having visited the Altar of Ylath earlier, the last seal in your way can now be opened and you can visit the prison. It's just a fort, really, so attack it (no problem) and rebuild it. Once you do that, there's another cutscene.
Last mission: attack Sorshan. The cutscene shows you where to go; a small path east of your upstairs town has a Seal of Sylanna, which you should be able to open if you cleared the middle island.
Before you go up the path, this will be one huge fight, so remember to visit boosters and gather creatures in a single army with your strongest hero. Summon caravans, check your items, call upon your oldest lore. The battle should be hard, but winnable.
If you're struggling, just reload, go back to the point before you broke the yellow seal and gather more creatures. I beat Sorshan in his town, with more creatures than he had, naturally, and with better stats. I used Firewall on his shooters, Fortune on my own creatures and then just sent my troggies and dragons in past the walls while my other creatures hammered away at anything that dared come out. The Regeneration spell is also nice here. But don't worry about conserving troops: once you finish this fight, the map ends.