[Kolorabi]

And run/sail around collecting stuff, while running from the monsters that protect it. Boost your leadership by finding flags, for instance. Early on, the islands are very difficult, but by finishing the fights in the other areas first, and collecting goodies without getting caught (remember to dig for treasure as well), you will get to a turning point where it stops being a problem.

Also, if you're feeling up to it, try to kill the kraken (talk to Mirabella at the eastern islands). It'll be a hard fight, but not much harder than what you're used to (bring loads of expendable troops), and you get tons of experience for it. If you also kill Lucky Jack (the guy in the mines - another hard-ish fight, but not really a problem), you can marry Mirabella, and get an extra bonus to any pirates in your army. With the flag you can get from the easy "her weight in gold"-quest (house next to Mirabella), you can give the pirates even more of an advantage - making them into cheap and very good melee fighters.