What is the optimal opening strategy for "Mortal Foibles of Kings"?
This map an unusual one. It starts with a lot of rat holes around your town, so you first have to defend from them. Follow this advices:
Don't build towers right at the start, they'll get destroyed before they get completed, it shouldn't be the first step in the game (unless you have a great tactic in your mind).
Recruit strong heroes, not rogues, and not only archers and clerics, you'll need tough units at the very beginning. I'll go with 3 warriors first, and some archers to have them leveled for future exploring. When you have 3-4 heroes at least at level 2, recruit 3 rogues. Don't upgrade any building yet, you'll need the money for the towers.
When a few heroes gain level 3, build 2 or 3 towers, and place them between the most amount of rat holes possible. Upgrade the towers as soon as you can!, they are the perfect defense for this map. I usually place buildings aside/behind the towers, near the town center. As game advances and basic towers get more expensive, focus on dwarf towers, but you should go with 4-5 upgraded towers unless game extends in time.
Construct/upgrade your blacksmith and market as soon as you see that heroes have earned money enough to buy stuff: build market/forge where heroes have 50-100 gold, go for market's healing potion at first, then construct the blacksmith. Upgrade market and go for the protection ring when they own 100-200 gold. This will bring you money enough to make expensive building upgrades like level 2 castle, upgraded blacksmith or dwarf towers. Some heroes start with a few coins, and will go straight for healing potions or a cool weapon.
Don't buy mage/cleric equipment in the blacksmith if you haven't recruited those units. Also, don't upgrade their equipment to level 2 if they don't own money enough. It will be a waste of money...
Start exploring by creating 200-300 gold explore flags, find and attack dens as soon as you resist the rat hordes easily. This is extremely important if you don't want to drown in future ranging hordes of big rats and skeletons and maybe a few bearman. (Try not attacking the bearman den until map is almost cleared, they can kill some level 2 heroes with just one magic shot).
When building trading posts, try clearing the surrounding area of patrolling monsters and nearby dens before doing it, and immediately upgrade them! Trading posts have some arrows at their level 2 to self-defense. If you can't clear the area around them, give 200-300 defense flag reward instantly to attract 1 or 2 heroes before the constructor peasant arrives and finishes it. You can remove the flag when completed.
Create parties to protect recently recruited heroes. Parties walk/attack/defend as a whole through the map. I.e. to protect low level mages which are extremely easy to kill if alone or attacked from the rearguard, and too expensive to recruit/resurrect.
Heal your own heroes (with healing spell) when the game advances, watch 1-5 level mages specially, even if you purchased their whole building spells before recruiting them. Mages tend to think they're strong enough when alone, but they're almost the weakest unit in game at low levels, thus they get killed frequently.
Before going for the caravan escort mission, upgrade everything in every building, even in the fancy market, every hero spell/ability/potion will be helpful to weaken and beat the Rat King. Also explore the map borders, some dens are greatly hidden and will give you some extra levels to your dwarfs, elves or mages.
Finally, when you attack the Rat King, remember to use the healing spell on wounded units, otherwise you may lose valuable heroes for future maps. Don't try to find the wounded heroes on the map, do it by clicking directly on the right top screen portraits and selecting the most wounded unit. It's good to know that your frosting and lighting spells won't work at all against the Rat King.
I've recently played it with my new laptop (buildings and enemy spawning dramatically increased) and here's the result :D
For the rest of maps, the best advice for starting a map is... ATTACK, EXPLORE, UPGRADE. Don't focus on defense for a regular map. Be a little more aggressive at this game (Majesty 2) than you usually are in others.
Attack, attack, attack! Start with the nearest enemies, do it as fast as possible, so every starting unit gets leveled as soon as possible and get some gold rewards. Only stop attacking on exceptional cases, while defending your castle, market or similar.
Explore at the same time you're attacking, with two or three archers at first, spend money if you need so, they will give you very valuable information of your next possible enemies, and map in general.
Don't spend much money on towers at the beginning, just to cover your back. Let units hold frontal town attacks, focus first on toughest enemies (with gold rewards).
If you find vampire yards, or other really hard units, erase them form the map before they start producing large amounts of unstoppable units.
Upgrade, don't forget it. You may have built enough units that leveled fast, but if you didn't upgrade your blacksmith and market, you'll be getting money slowly, thus not letting your units get better stuff as game advances, leading to a terrible defeat. Keep them in mind, focusing your economy on the money coming from heroes buying items is almost essential at the late beginning. I think that, with a bunch of heroes still alive, it's better to upgrade your marketplace than resurrecting a level 10 warrior.
Meh
To build all that stuff you you'll need to exploit a speed-bug that is removed AFIK.
Build a Mage tower in front of the castle, then one magic tower at the right. When house at the left is destroyed, put a magic tower there.
Keep 400 gold in your coffers at all time in the beginning so that you can keep the towers enchanted.
Then it's a bit of a slow waiting game.
You might want to recruit mages, one at a time as you get enough money to recruit and have 400 in the bank. The activated magic towers means that they tend to survive. With a couple of mages at level 7ish, you can ask them to destroy dens and make it safe for other building than towers. Such as a marketplace.
You can use the magic towers to defend the building of regular towers. I's pretty tedious until you get a marketplace, then it should be a breeze.
I'd recommend expanding downwards.