First, I have to say that my friends and I really enjoy the game in its current state. We discovered it on Friday and have hardly been able to put it down since! We vanquished the first overlord last night.
That being said, I came up with an idea that would make things interesting for exploration while being entirely optional. I don't know if the idea would work with the way the game currently generates chunks and regions, however. Here's the idea in a nutshell: have some warp gates very rarely contain another gate within them (perhaps called a wormhole). This wormhole would have two functions:
1. Like other warps, a wormhole would let you warp to any other discovered wormhole. However, instead of being restricted to the current world map square, you can warp between wormholes all over the current continent. This is a convenience factor, but on its own has little importance since the world map is risk-free. However, to expand on this I'd humbly suggest two other changes:
a. There is always a wormhole within the settlement, so finding one deep within a cave makes it even easier to go back and heal.
b. A wormhole that's been discovered causes its square to be considered a candidate for a wind shelter (it is "adjacent" to a safe square this way). This makes a potential reward for exploring stormy squares because it is more efficient to place shelters in the middle of the storm than on the edge of it, but people who didn't want to take that risk can still use the old method.
2. The other thing that would be cool would be to make the wormhole "enterable", treating it like a side link. This would link it to one other wormhole elsewhere on the continent. This would be a stable link, but would add an element of surprise for exploration again, for those seeking one. Who knows whether you end up out in the ocean or deep under a lava flat? You always have that invincibility from standing still in a new room, so there's really no risk involved, just fun! This is a part that I'm not sure could be done with the current map generation (because I understand it's done on the fly, and piecemeal)... how hard would it be to "place" a wormhole in an unvisited region? Say, roll some numbers when you enter one, so you know it's on map square X,Y, in surface square Z, and probably at a cave depth Q... and then generate the other layers as you explore upwards or downwards from that point?
This post is long enough as is, but I'll end by saying this seems like a neat way to add surprise that is still optional for people who didn't care, and hopefully wouldn't be a pain to implement... though I could be very wrong.