I tried that mission at least 3 times, and just can't get too far. Help?

In the last attempt, I took the first city pretty fast, built up until Efretti, flagging the sawmill and ore mine in the meantime, then went east to grab the enemy city (who already had Cyclops, but I managed to beat him anyway). Pretty much immediately after that, through the portal in the south, comes another computer hero with (among other units) the f... riggin' Behemoths.

Just what for all the hair in Blackbeard's beard am I supposed to do, break my non-existent wooden leg at him?!

You mostly need to go faster - the enemy generally won't attack if you have a sufficient force nearby to defend a town. I know that sounds like an impossible task, as you have attempted to go as fast as possible already, but there are a few ways you might be able to kickstart the map:

* Skip the first (Chaos) town - it's isolated and actually has better defense than the second (Might) town. Come back to it later when you have a bigger force to take it easily
* Avoid a few of the optional things until later, like the seaman's hat at the beginning
* Time your turns so that you make the most of each movement point

After you take the second town quickly, things will get a lot easier.