Simple: A new world type called Cavern or somesuch.
Superflat is a few blocks up and has over 250 blocks of sky up, right?
Cavern would be solid stone up to layer 250, then air. You would spawn on top, and build a bunch of underground structures. It would generate dungeons, strongholds, abandoned mineshafts, and caves unless you turn off generated structures.
This would allow for much larger underground structures to be made.
Just a simple little idea from little ol' me.
Suggestion by Sutinen: Underground villages for this mode, which would work wonderfully for my plans, and save me a lot of effort in building the villages myself.
Not what I had in mind when I read the title, but it's pretty cool anyways.
I was thinking a world that's entirely underground, you spawn in a cave with 2 stacks of wood and a sapling, and this cave goes on forever. It'd be great for survival map makers and people who want to do something a little extreme.