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.