I have a radical idea that could make this mod really cool.
What if the map was divided into two halves, this world and the underworld.
The underworld would be almost impossible to get to initially, and populated with barbarians ranging from goblins to demons to fiery dogs. However, it would also be ruled by an unplayable demon Civ. The main way to get to the underworld would be a wonder that made the underworld no-longer impassable. Then you could go explore and have adventures down there, but you wouldn't be able to build any cities there.
This would also give the Ashen Veil its coolest advantage. Starting when the AV was founded, its founder (if they converted) would get the choice to "exploit the underworld" or not. If they chose to, they would be able to teleport 1 unit per turn from the holy city to the Demon's capital, whihc would be shown. This would give them a large advantage.
Also, their "hellgate" terrain types which I mentioned earlier would also be able to send and receive units from the demon's capital city. Its like sending a unit through the underworld so he doesn't have to sail around the world!
However, the downside of them accepting the demon's offer is that they would have to be the AV for the entire game.
If they declined the offer then the next civ to convert to the AV would get the choice, but each civ would only get the choice once.
The other way to get to the underworld early would be a national wonder produceable only by a civ following Runes of Kilmorph. It would be called something like "Dig for the riches of the underworld". It would spawn barb "underworld" units nearby every so often, as well as give the Dwarves access to some special resources only available in the underworld. It would make them more friendly with the Ashen Veil, but less with the Order.
Now that I give it even more thought, there could be some early heros that allow you into the underworld as well.