I remember Civ II: The Test of Time; the Fantasy gameplay was my favorite. The one based on Norse mythology.
I got it after enjoying Civ III, which eventually lead me to acquire Civ IV and upload Fall from Heaven II. A squeal to the Fall from Heaven mod.