Use the Customized map option to create more UHC-friendly terrain generation

The customized option in the create world dialog contains an overwhelming set of features.  But with a few tweaks you can make changes that will dramatically change UHC experience.

Detailed information on the customized settings can be found here:
http://minecraft.gamepedia.com/Customized

These instructions are for Single Player new world creation, since it is easiest to tweak the settings here, make the world, and then move it into a server.  You can also make changes to the new world generation settings for servers with the server.properties file and a custom string but this is a lot more complicated and harder to play around with.

Step 1:

Remove Unnecessary Structures

Often in UHC, there are tweaks to the game to encourage players to spend less time underground, more time above looking for a fight.  It hardly seems fair for a hermit to win after all others kill each other in battle.  There are several things in terrain gen that can be tweaked to encourage a fair experience and more time above ground.

Villages and Temples are great for encouraging above ground exploration, and reward the first comers with potential game changers. I suggest leaving them in.  However you can select to increase or remove dungeons below ground. More dungeons, more saddles, may encourage exploration. Water Temples and Strongholds are also good candidates to leave off if you choose to make the game more balanced and less solitary.  

Step 2: Ore generation

Caving can sometimes leave players, by luck alone, spending all their time underground just trying to gear up to go out.  This means that tweaking ore generation may be one of the most powerful ways to encourage surface play.   You can also increase the max height of ores and diamond to allow prospecting of open land and cliff faces, however deviating this much from vanilla may be too jarring on the game.

I suggest leaving the spawn heights as they are, and then increasing the spawn tries.  Diamond and gold can be 2x-4x higher than they are now.  Iron would probably be over abundant with anything more than a slight increase.

Step 3: Optional, for rugged terrains

Set Height Stretch to 50 (max)

You can make maps much less rugged by increasing the height stretch.  This setting is also less work for the generator when turned up (and more work, higher terrain if lowered)  It is at 12 by default and when maxed out at 50 the terrain is a lot less severe.  Sometimes new, unmapped villages may appear because Amidst doesn't show some villages due to terrain.