I simply love the idea of amping up the exploration aspect of FFH. Adding a few ideas to the pile:
Large patches of Wastelands/Badlands that remain in barbarian hands until the endgame. Littered with the ruins of a civilization from the Age of Magic, before an unnatural calamity turned green lands to lifeless plains of rock and dirt. Don't pose a problem to Infernals.
Ice plots representing permafrost and glaciers, much like they do now. Could be home a whole host of things: madmen who believe the Age of Ice never passed, Frost Giants, the last survivors of those Illian-aligned goblinoids from the AoI scenario... Immediately explorable by Illians.
Thickets of Deep Woods, home to woodland creatures both malicious and... well, neutral, I suppose. These served as rare havens for once far more comon magical creatures during the Age of Ice. Generates Ents, Fyrdwells, etc, and could be the catalyst for a whole host of events if they lay within your borders. Negotiating with its denizens might get you some neat units or unique resources - angering them... not so much. Easier to deal with if you're Ljosalfar/Svartalfar or following the Fellowship.
The Depths - the deepest of ocean trenches, where it is said the Overlords hold their council. Simple sailing trough these waters is known to have driven men mad. Spawns krakens. Can be the source of 'Visions' for civs following the Overlords.