I'm looking for a little help from (hopefully) like-minded gamers.

If you like games like the Civ's and Age of Empires, what games would you recommend for me to try next and why?

I'm looking for games that have great replayability (I tried Black and White and it was good but there is no replayability.)

Hearts of Iron 2. WW2 Grand Strategy. It's great, but it has a rather steep learning curve.

Along those lines, probably Europa Universalis II (or III). Sort of like Civ, set between the 1400's and early 1800's. Has you take control of a civilization and have to guide it through several decades in whatever fashion you like.

Several decades being something like 300 years.

Stronghold (the first one) is a very good castle oriented game.

Rome Total War or Medieval 2 Total War are also very good games, with RTS battles and a TBS world map. Although M2 requires a decent computer. If you get RTW make sure you get the gold edition that has both RTW and the expansion (Barbarian invasion).

Medieval 2, GalCiv2, (way back machine) Age of Wonders Shadow Magic, Armageddon Empires, (if you can struggle past the clunky User Interface) Dominions 3, Team Fortress 2 (okay, this won't meet your criteria, but it a favorite at work).

Which ones of these are turn-based? Also, I am more into building an empire than taking over others (or defending mine) with armies.

I am partial to turn-based because I like to take my time. No matter how slow I could turn down AoE it always seemed to fast after playing Civ my whole life.

Well AoE is knid of, well, SPAM. The best tactics with AoE is to spam buildings everywhere, which I cannot stand.

All of the ones suggested so far (except Team Fortress 2, it's a face paced first-person shooter) are TBS though Total War series and Dominions 3 have RTS battles (but you can't control anything during the battle in Dominions).

They also all have you starting out small (except with the Holy Roman Empire in M2 which is already fair sized) and expanding through conquest. (With other non-violent possibilities but conquest is still probably the easiest).

Rome Total War or Medieval 2 Total War are also very good games, with RTS battles and a TBS world map. Although M2 requires a decent computer. If you get RTW make sure you get the gold edition that has both RTW and the expansion (Barbarian invasion).

Are the TW games good for a player who likes Civ?

I've heard great things about those games.

Total War games are pretty good and they also work by turns. The Paradox games aren't turned based, but you can easily pause the game (while still executing moves or responding to events) as well as advance game time quite slowly.

Total War games are pretty good and they also work by turns. The Paradox games aren't turned based, but you can easily pause the game (while still executing moves or responding to events) as well as advance game time quite quickly.

Fixed.

Yeah, the Paradox games are almost turn-based because you need to pause a lot (and it's very simple to pause and unpause).

Yep, and you can breeze through the years in rather short order (unless you have an older system, but I don't think it could be so unbearably long on the fastest setting).

That often happens during times of peace as a smaller country. The larger ones tend to get many more random events (and some not so random) breaking up the good times.

When it comes out, I highly recommend Pirates of the Burning Sea. It's like Sid Meier's Pirates! but a little more serious art style, PVP action, and the ability to make your own ships and things. Plus I talked with the developers at PAX 2007 and they're keeping the game open to expansion to other places of piracy.

But that's a pay per month scheme aint it?

Yeah :\ 10char

Another vote for GalCiv II (turn-based, combat doesn't play such an important role as in most strategy games) or Alpha Centauri.

When it comes out, I highly recommend Pirates of the Burning Sea. It's like Sid Meier's Pirates! but a little more serious art style, PVP action, and the ability to make your own ships and things. Plus I talked with the developers at PAX 2007 and they're keeping the game open to expansion to other places of piracy.
Yeah, Pirates of the Burning Sea will be released on January 31, 2008. I have preordered it
http://www.dealstudio.com/searchdeals.php?deal_id=65949

Disciples 2 Gold, including the expansions is worth getting if you can find it. A bit old, but fun and very nice artwork.

Disciples II Gold is easily found on both Steam and Stardock.

Yeah, Pirates of the Burning Sea will be released on January 31, 2008. I have preordered it
http://www.dealstudio.com/searchdeals.php?deal_id=65949

I wish my computer was powerful enough to run it, that game looks awesome.

Pharaoh
Colonization
Alpha Centauri

I second Galactic Civilizations 2 and Dominions 3. Both of those are excellent TBS games worth looking at if you like Civ 4.

Tabula Rasa (http://www.rgtr.com/index.html) is fun if you're into MMOs

Since Colonization is hard to find, FreeCol is an excellent alternative. Domestic colonization and working with the natives is a must.

I would recommend Timeshift if you don't mind that the game is pretty short for $50. The effects are awesome though. Encountering a group of 20 soldiers, pausing time, shot gunning them all in the head at close range and resuming time is very satisfying.

Recommended: World in Conflict!

It has:

Great replayability, wars between Amiricans and russians, great graphics, active multiplayer, cheats, easy to play campaigns, easy to learn interface and great storyline!

Description:

It's nothing like seeing your enemy infantry die in your barrage. Nuking is also a good strategy. Also, seeing your enemies being wiped out one by one by your carpet bombing will earn you a lot of points in MP. And only one thing: beware if your enemy is an expert. Real time because you play it in the field already and has different roles. Very flexible armies.

Genre: Strategy => RTS => Real Time

This is a recommendation.

I've always been fond of city building games and of course, Sim City's the staple franchise there. I think Sim City 4 is incredible, but 3000 is a very solid game and it would be cheaper/less demanding on computer resources. It would be hard for me to go back, you have so much more control in Sim City 4, especially over the budget, so it's much easier getting started. Sim City Societies comes out this week too, that sounds interesting. I just hope my computer can handle it.

I love Tropico too, another great city buiding game, with a political aspect to this one too. It really has a lot of replay value because there's so many ways to play it. Play as a communist, play as a capitalist, play towards the tourism goal, the corrupt personal wealth goal, and more. I never played Tropico 2, it didn't seem to have the same things I loved about the first, and it seemed like the reviews weren't as good either.