I cant comment as I havent played the Age of Empires.
But civ is great, also if you are looking more battles, less city building you can try the total war series. Rome and Shogun are great. I own medevil but have never played it.
My first Civ experience was the following.
My firends dad worked at a small surveying company. On Friday night we went to his office as the computers were networked with COAX
We started playing this civ game that my buddy bought at the Bay in Edmonton.
We wet to 7-11, got some slushes and other items, started the game around 9pm, his dad came back to check on us, and it was 8am the next morning, I hadnt noticed it.
The game should be on the FDA list becuase its more addictvie than crack - oh sweet columbian ice.