Personally, I prefer Civ over Colonization. However, CivAGA is badly programmed and not very system friendly at all. FreeCiv uses MUI and is very compatible, but it can be difficult to get up and running. I'm not sure if there's support for computer players (If there is, I haven't figured out to implement it yet; maybe I should read the manual).
I've not played Tales of Tamar, so I can't speak for that.
Depending on your definition of strategy, you might also consider the Bullfrog games: Populous, Populous 2, Theme Park, Syndicate. Worms was initially considered a strategy game upon release...