Check out 'Elevated' - winner of the 4k PC demo category at Breakpoint 2009. It's a fly-through of a realistic looking procedurally generated terrain model with music and some fancy post processing effects all squeezed into a <4096 bytes executable. Even my moderately high-end PC can't run it (I suspect because it shoves an overwhelmingly huge triangle mesh at the GPU) but there's a video here:
oh RGBA, I was expecting someone would post elevated in a thread like this. Here is a homepage from IQ from RGBA http://iquilezles.org/www/ - lots of useful stuff here. He is working, I believe, on Infinity engine (not bioware one) which will, hopefully, yield a game like EVE/Elite one day. Here is a devlog: http://www.infinity-universe.com/Infinity/index.php?option=c...
The article is mostly about rendering terrain, not generating it, and it also has nothing to do with reddit.
However, the rendered results do look relatively nice, and the article (even as awfully paginated as it is) gives a pretty good idea on how to get there from zero.
The awesomeness lies in the explanations and reasons, not the intrinsic tech.
This guy is currently doing a series on procedural generation of a city terrain, and it's the same deal. It's not going to win awards for "teh aw3som3st cty evar!", it's that you don't often see someone do something like this while posting reasons, dead-end experiments, and other such commentary.
It's less awesome to look at, but radically superior as an article to read and learn from.
http://www.youtube.com/watch?v=_YWMGuh15nE