Dominions 3 - Basic graphics, very deep strategy, quite high micromanagement.
Age of Wonders: Shadow Magic - Low on micromanagement, high on fun. Very similar to Heroes of Might and Magic series in style in that they have basic city building, capturing points on the map is important and tactical battles.
Master of Magic - Like Civ series but with magic. Good fun and free but is dated.