I added much to the game in the form of Divination. In my opinion, exploration is handled extremely well in Civ games. So why not have a few options to get some really powerful magic exploration? My Eyes of the Eagle spell reveals 12 tile radius of the map. It is random bag to get Book of Winds, but when you do, you can do some serious scouting and you have a nice intel option during wars. I encourage the AI to use this alot, if they don't have full knowledge from the difficulty.
I also have a Divination ability for Mages. Then there is an endgame spell to reveal the whole map as long as you pay the maintenance cost. This kind if addition would probably be nice once the player is past making scouts to gain constant intel or search out large maps.