Yeah, Call to Power was a fun series. SMAC is also worth a look. I would also suggest Age of Wonders 2: The Wizards Throne. (There is another one called Age of Wonders 2: Shadow Magic you may check out - but I cant recommend it from personal experience because I havent tried it out yet.)
Some things that stand out in call to power that i thought were very fun;
1) You can form armies any time you like and then when they do battle, ranged units stand behind melle units and pound each other just like real armies would.
2) underwater cities
3) Tile bonus items can be traded for money, and the trade route can be pirated!
4) In the earlier stages of the game you can build slaver units to capture enemy settlers, population from enemy towns and even enemy armies if you put a slaver with your own army that wins a battle! The slaves show up as bonus workers in your city screen.
5) mag tubes - super roads that can be built on land and sea
6) Public works - you can select an amount of production to be spent on building improvements like mines and roads (no workers).
7) There are farms and mines like in civ4 but with improving technology you can 'upgrade' them, there are 3 upgrade levels. In civ4 there are a total of zero upgrade levels for mines and farms., what you build in the stone age, thats your lot.
8) you can change any terrain type - like in civ2 except more extensive choices.
9) you can build things on desert terrains and mountains.
10) call to power 1 has a space dimention with space cities and spaceships, but it got nerfed in call to power 2, i dunno why? (probably because the AI couldn't grasp it properly).
Yea so the main thing that rocks in call to power that puts civ4 to shame is the way armies work and the battle screen.
The main thing that stops the game being better than civ4 overall is the docile AI
Edit:, correction - somone new to the game would probably find the AI very challenging!