Populous: The Beginning. I still play it from time to time.
The game itself is rather easy, but still fun; you get to build up your tribe, increasing your Shaman (main unit)'s mana, enabling her to cast deadlier, more complex spells, the most lethal being the Volcano (note: The pic below comes from the Internet):
Usually, I just wait 'till my Brave population goes to 199 (the max pop), so the Shaman gets uber-strong, with most spells recharging quickly, and then solo the enemy with JUST the Shaman, wreaking havoc by casting a plethora of destructive spells (oh and primitive as they are, Shaman on a Balloon is just badass
Oh, and just a sidenote, it's slightly surprising that VERY FEW here play the PC game called "Pirates of the Caribbean", since only one replied to its thread. That sure is an old, abandoned game
But fortunately, there's a modding site dedicated to it.