Immortal, no patches:
Instead of building the first couple of cities on the water, I moved northwest and settled the capital next to the 3 gem mines and Dunwitch next to copper and horses a bit northeast from there. You always have time to expand back to the water, but if you let Perp beat you in a territory race you're never going to expand there. Since Perp gets OO quickly, I got RoK. In a game where you're actually going to need to defend your cities a lot, Arthendain is priceless. With guerilla 2, combat5 and a few other buffs and promos, he quickly gets to around 50-55 effective defense strength in a hill city (and you're smart enough to only settle on hills, right?) Destroy undead is also excellent because you start right next to the very strong infernals and they use a lot of diseased corpses. The paramanders also get a bonus against demons, and since Sallos is the biggest threat to you from the start, RoK is a no-brainer.
In my game, about half the civs went OO and the other half AV, which allows for an obvious exploit: Casting destroy undead with an undead unit nearby immediately declares war on the injured civ. It probably works with maelstorm/tsunami as well, easily allowing you to declare war on whomever you wish. I personally didn't use it, but it's there just FYI.
There's a lot of mana on the map, and with conquest+apprenticeship and maybe theocracy you can get mages quickly. Thus, for magic I recearched necro. Entropy gives you rust which is an incredibly powerful defensive spell at 1st level. It can stop a city assault on it's own. Shadow 2 should be useful (a buff that ignores terrain defence) but I don't think it worked as advertised. Then, you build death nodes all the way and get the Tower of Necromancy. Once you've got your corner cleared (the Hippus and Sallos) which should be doable with RoK, you should have enough for 10strength specters to take care of your offensive needs.
From here on it's archers and Arthendain on defense, Guybrush, Bambur cats and swordsmen/paramanders along with scepters on offence. Don't forget that Bambur can heal catapults on the go, which means you can kamikaze them at full strength on every city you take. I actually lost Bambur pretty early (I'm very proud I didn't reload) and still managed to roll.
If you've dealt with the demons and lost Bambur or Arthendain, you might consider a switch to Empy to get Chalid and Rathas which are more useful than paramanders against non-demons.
I got lucky with a tech or two at the start from goody huts but was subsequently dogpiled twice in a row because I led the score. In general, I think the scenario is very beatable even on Deity, you just need to be ready to defend a dogpile at all times and have an offensive stack ready BEFORE war is declared.
One last thing: Guild of 9 is absolutely the best wonder in the game for defensive purposes. You can keep just two archers in every city, and they turn into 8 defenders within the 2 turns it takes the enemy stack to reach you. Since I had Arete and conquest+apprentice throughout the game, it means 6 strength 7 mercs with guerilla 2, plus the two archers. That saves you the time and upkeep on having 6-7 archers in every city, and requires only around 500 spare gold at all times. The gold is also easier with RoK temples.
Just my 8 cents, have fun.