Well, much of the game is already Fantasy, but I really liked the Atlantis scenario for Civ 2, and there was another that was part Fantasy. It had the Native Americans developing all sorts of cool stuff including chocolate (for Happiness) and observation baloons.
The Atlantis one had an exploding volcano that was random and could wipt out (almost) the Atlanteans. If you were not the Atlanteans it added an interesting random element; if you were, you could turn it off. Many interesting and mythical units too. It didn't pretend to be historical and was enjoyable.
Hey, the more Fantasy scenarios the better. I wouldn't have to get PO'd at the basic game's lack of realism. Go for it!