I really recommend trying Civ IV. The Complete version of it (including the Vanilla game, plus its two expansions Warlords and BTS, plus its spin-off Colonization remake) is still quite easy to get, usually cost not more than 10 Euros, Dollars or Pounds or so (so if you don't like it, it's not too much money wasted) and really is massive in its content. Have a look here, the Civ IV part in this package does not even have the disk copy protection:
http://www.amazon.co.uk/Civilizatio...T826/ref=sr_1_1?ie=UTF8&qid=1352715893&sr=8-1
Especially BTS is considered by a huge part of the community to be the best, deepest and most complex part of the franchise - and if that should be too much for anyone there's still the "streamlined" Vanilla version to get used to the game. The game development team - as far as I can judge - took quite some effort listening to community feedback when fixing bugs, improving gameplay and adding new features - and I think it shows in the quality of the product we have now. Also there was quite some effort on working multi-player support.
Another great feature of IV is it's open structure and the way the developers and the fan base expanded on the main game: even the base package comes with quite a handful of good mods (for example the Space Mod called "Final Frontier") and scenarios (WW2, Ghengis Khan, Charlemagne, Unification of the Chinese Empire, etc.) - and there's fan made must-have stuff like "Fall from Heaven 2" (high quality fantasy mod), "Rhye's and Fall of Civilization" (a mod with fixed and enhanced game rules to recreate real world history), BUG and BAT mod (improved user interface / improved grafix) or the TAC expansion for enhanced gameplay in Colonization. No need to say there are zillions of fan made scenarios, units, civilizations, leaders, mapscripts, game rule changes / improvements, fixes, improved AI and other stuff.
For me sure IV is the part I spent the most time with and which is still the most fun to play.