Strategy
Big Picture
I see there has been some discussion about attacking early or attacking late. I went for the pretty late. I launched the attack around turn 300 and won around 450. The Orc island to the south was empty for me; of course, in my second play I had an unfair advantage in that I knew the island was there and that it was empty.
Clearly, the idea for a late attack is to build up. For me, I wanted to wait until I could heal before attacking, which ultimately meant getting high priests. I went for the overlords because I thought naval superiority was crucial and Stygian Guards are probably the best unit they can heal and use weapons. .
Naval Superiority
Indeed, my first game I got badly hurt since the AI crushed me with Privateers early. My pirate coves were smashed, as well as my sea resources, and this crippled my economy. I played on for a while, but never got true naval superiority. Later, Tebryn build a 10 15 15 ship invasion fleet and attacked the Southern island! I didnt know the AI could plan this! They took a key city (which I now cannot counter-attack!) and I started over.
My second game, I got Optics as my second tech after writing (to get the supplies into Libraries). This allowed me to build the Black Wind and some caravels. I did manage to keep naval superiority the whole game, but I obviously I spent a lot of resources on it. I also got Octopus priests and raising parties, and stole his fleet. Guybrush probably took about 6 ships.
Wonders
I think the wonders were the key to victory for me. I know many people feel in a regular Civ IV or FfH games that building wonders can be a mistake; it slows down building troops, or settlers and workers, which can be more important. But The Black Tower is different!
First, in a standard Epic game, they can indeed slow down expansion. But in the Black Tower, if you do a late attack, your expansion is pretty much limited to the two islands anyway and fairly soon they will all be settled. Secondly, if you are playing with 7 opponents, your getting the wonder keeps one of 7 players from getting it; you get the benefit of the wonder if 5 -10 cities, and more later, and keep one player from getting it. Here, every wonder you get keeps the other side from getting it. Especially for wonders that impact every city, once fighting started, on a large map, I can get the benefit in very may cities and keep the Sheaim from almost as many.
So, in my second game, I started by building the Heron Throne my capital was going to be my wonder city and it gives a hammer boost. Since I build the Black Wind, I got a level 6 unit quickly, and I got Form of the Titan. Again, I probably build some 400 500 units and Tebryn maybe as many; I bet it impacted over 1000 xps.
The Big Three
Three wonders were dominant.
The great Lighthouse: With intercontinental trade, I probably was getting 5 - 6 GP/trade route later in the game (I admit having Inns and Taverns). With maybe 40 50 cities in the mid turn 300s, this gave maybe 500 gold per turn and probably kept the Sheaim from earning very large amounts. Between the gold it generated for me and it kept Tebryn from getting, it may have generated 100,000 gold or more. Get that lighthouse!
Guild of Hammers OK, we all know how good this is!
The Nexus This was also absolutely critical. Without it, holding territory and deflecting attacks is very difficult. Now, wherever a threat comes, just Nexus in an army. I also got the Guild of the 9, with my outrageous economy it allowed me to build many mercenaries. With the Nexus and the guild, I took cities instead of burning them
The Next Most Important Wonders
I was lucky that Gosea had built Nox Noctis; I captured it very early. Although this isnt equivalent to Tebryns ability to strike without retaliation, it is probably the next best thing. I can kill people straggling outside of cities and not get hurt; workers can work any tile with impunity. With naval superiority and Nox Noctis, I had only to defend my borders, and with the Nexus, I could move ahead.
The Shrine of Sirona Normally a secondary wonder, here it lets you HEAL! I was then really pissed when I found the Sheaim had built it!! Fortunately, again, Gosea built it and I took it early. It is especially useful for healing living units that arent in the main stacks with the high priests casting Heal.
Form of the Titan Mentioned above
Tower of Eyes I didnt get bad war weariness. By the end of the game I was still on city states with a 20% luxury slider, but it can help to have the dungeon in every city.
Guild of the 9 - It is more useful once you start attacking and winning, because by then you should have a lot of money and the mercenaries can help.
Others
I got most of the religious shrines; these were useful early when I needed mana sources and later for general power. I got a bunch of the others, but these were the crucial ones.
General Strategy
Originally I thought I would do my attacks with my non-living units, my main armies were maybe 70% Stygian Guards and 30% Iron Golems. I got Barnaxus to power 5 and then sent him to my capital. But the Guards were stronger.
Nonetheless, I did wind up having my main attacking stack living units; the haste ability is just too important. I would bring up slower troops, by the end of the game I had about 170 Stygian Guards and 60 Iron golems. But these would largely be assault troops and hold my cities and Nexus in. My main army had my heroes, 2 high priests, and my most powerful mages and archmages. (Not my liches).
Like everyone else, with naval superiority, I used my ships to bombard the city defenses, and my cultists to cast tsunami form the sea, and coastal cities were easy to take.
My main army in the Gosea area was subject to the most attacks. This army was maybe even stronger than my main stack. I had to spread between 3 cities. By the end of the game I had very strong Stygian guards, many 10th level or higher. The key to defending is to have 2 mages who can cast Maelstorm and maybe destroy undead. This defense was repeated as I defeated the other Sheaim.
Get a temple of order in your biggest city (I had one city with the Tower of Complacency and about 30 people). Use Donals ability, and you get about 20 units/kill. I would kill a baddie, nexus him out, cast rally, get him back, etc. The hardest part was the logistics of getting all of these unit to the front. You have to move them to other cities so you can nexus them out fast. Later in the game, perhaps form laziness, I would just rally in a local city to avoid the logistics problem.
I had one high priest on a secondary front. I would take wounded units, nexus them off to him, he would heal, and they would go back.
Magic
It is hard to get a lot of mana before the big attack. Here the shrines and the wonders can help I got the soul forge to get an early death mana which is necessary for liches.
Your units that are earmarked for liches cannot be in the main attack because of the need to cast destroy undead. Therefore, they need death to become liches, but get spell extension, maybe SE II, so that they can stay behind and summon killer units. I used them mostly for defense, they cant be hasted and keep up with the main army anyway.
Another wonder I got was Catacomb Libralus, but I dont know if it is needed. Most of my mages were from the Luchiurp, I was spamming them. Just as your living units cannot heal, your ships and golems can be instantly healed with a bunch of Luchiurp adepts casting repair.
The ideal fleet set-up was to have a Cultist and a Luchiurp adept with repair and fair ewinds and you will rule the seas! Unfortunately, real life games and ideal play arent always the same thing.
As always with a game where the attack will be late, and there is time to set-up, build the adepts early. You need a lot of mages here.
The biggest risk at high levels is the mindless damage from the pyre zombies. Therefore, you always want to get the two maelstroms and lots of destroy undead spells. Fortunately, you start with air mana. Therefore, early mana builds are enchantment (happiness, repair, enchanted blade) and life.
For the archmages and especially liches, get metamagic. By the end of the game my Djinns had a strength of 30! Its a big map and if you start to take territory, you get a lot of mana sources.
Your defense stacks should be packed with these magic users and watch the attackers melt away!
Civics
Although it is considered bad form, I ran god-king for a long time. Why? It is the wonders and the need for some speedy builds. Once I got the Guild of Hammers, I had most of the Southern Continent build up and I needed City-states.
I went for the moolah; consumption, guilds (apprenticeship earlier), agrarianism and then guilds, and undercouncil.
By the time I could attack Tebryn, I had 5 armies circling. I doubt it took more than 10 -15 turns to finish him off.
The big attack
In my second game, Tebryn also came after my southern Island with a 10 15 ship group; but this time, I was ready. I had about 5 -6 units in the facing coastal cities; but more important, I was watching. I had sentry ships out in the ocean! As he was one turn from landing, I cast Raging Seas! I then clobbered them.