Haven't tried AoE3, but Civ4 is a really great game.
As for the difference between turn-based and real-time strategy, aside from what Ghostavo said, it's really about the whole approach to playing:
In Real-time games like starcraft, speed, precision, reactions and a sound build order count for at least as much as actual strategy does. Indeed, there's little strategy in real-time strategy. It's mainly tactics.
Whereas in turn-based strategy games, strategy is everything. You never need reflexes or speed, as when it's your turn you have as much time to think about your actions as you need. for this reason, the scope for turn-based games is also much larger, as you have the time to deal with far more. The downside is that if you're looking for action, there is effectively none. Once you order units to fight, the outcome of the fight is in most games out of your hands.
There are exceptions to both of course, as well some games that blend the two genres somewhat.