Consider adding underground features

[mathuin]

Start with caves. Learn about something called Perlin worms. http://gamedev.stackexchange.com/questions/33590/how-to-generate-caves-like-minecraft talks a little about what's going on.

After that, figure out how to create dungeons. Replace the occasional cave terminus with a mossy cobble room containing a monster generator and a chest with random loot.

If this works out, then add "lakes" somehow. Maybe water and lava? Depending on depth? Not sure.

And then there's abandoned mineshafts.

Maybe someone else can do this. :-)

[mathuin]

orphu/mcdungeon does the dungeon creation stuff really well. If someone else could do the caves, I'd be all set. :-)