The second scenario, the Rusted Desert, will prove a logistical nightmare. It is basically a vast empty area, full of resources, mines, artifacts etc., mostly unguarded. Well, when I say unguarded, I mean "unguarded by permanent guards". You will get your share of neutral armies, sure enough - scattered across the desert are perhaps fifty, perhaps even more patrolling neutral armies with 80+ Nomads each. You will not be able to beat them right away - cleaning the area will require some major hit-and-run attacks, accompanied with serious drinking of Potions of Immortality. Don't even hope to fight the Nomads without first attaining GM Combat and either at least expert melee and/or some significant Medusa stacks of your own.
The good news is that patrolling guards mean that almost all mines can be captured by a single level 1 hero, if he is lucky enough not to get attacked. You should try to reach the gold mine in the north-western corner as quickly as possible. Which reminds me, take care to actually EQUIP the artifacts you got in the last map...
Your main task, apart from avoiding the nomads, will be to crush the necromancers and befriend the Megadragon. The necromancers have three cities, located in the center, in the north-center and in the center-east. They do have some formidable armies and strong heroes (two level 17 and one level 23), but you can pretty much forget about them, as they will be so scared of the Nomads that they will just back to their towns and stay there. Fortunately they don't have any shooters, so your direct damage spells will take care of them quite well. I would still recommend stacking up on Potions of Immortality and some fodder troops; 6x1 Nightmares (good for scaring the enemy heroes) stacked around Spazz turned out to be quite effective.
The strongest of the necromancer heroes has a Dragon Scale Shield and Armor, which you will need to get the Megadragon's favour - perhaps it is a cannibal. It will also need 100 Sulfur. Once you get all this, and clear the two arenas (one in the north near the Gold mine, the other in the south, east of your southernmost town), go to the Megadragon area in the south-west. Don't forget to relieve one loose Megadragon of his hoard of Armor of Death, Snowshoes and Supreme Crown of the Magi, you will need them in the last scenario.
Spazz is limited to level 22. I focused on improving his Chaos skills, almost maxing him out (only master in Sorcery). The remaining levels went into the Combat skill.