Screenshots:
http://kschnee.xepher.net/pics/070808island.jpg
http://kschnee.xepher.net/pics/070808nations.jpg

Here's a working version of the diamond-square algorithm code for your
use, using a power-of-two + 1 approach:
http://kschnee.xepher.net/code/diamond_square.py

I tried to implement the idea of reducing the randomness by a factor of
about 1.41 (square root of 2) between each step, but it looks from this
code like I accidentally didn't actually use it! I don't see the ridge
effect mentioned earlier though; the result looks good. The height
values are now 0.0 to 1.0, for arbitrary smoothness. Watching the
program go is fun. If you don't have it display each step, though, it
can generate 513x513 terrain in about 5 seconds.

The code also includes an ErodeTerrain function based on that paper, but
it doesn't seem to work right, consistently blurring stuff towards the
right instead of all around. The error is probably something stupid.

See also:
http://kschnee.xepher.net/code/shrubbery.py

The main attraction here is a function (PaintTerrain) that color-codes a
loaded map based on height values, making it look like an island
landscape. Also included are a function for painting some "national
borders" using a Voronoi variant, and stuff for
loading/saving/converting heightmaps. The screenshots above are from
feeding diamond-square data into this. PaintTerrain is a simple way to
try rendering any experiment with heightmaps.

In hindsight, maybe it should look at slopes as well as absolute 
heights. Another upgrade would be to make the terrains relative. Pick, 
say, 100 regularly spaced points on the map, sort the heights, and set 
the water level such that N% of them are below it.

Also:
http://kschnee.xepher.net/code/voronoi.py

This one's a demo of the Voronoi algorithm for making a bubble sort of
thing. It's not a good implementation, and it includes commented-out
earlier attempts that produced weird but interesting results.

As I've said, I've been wanting to make island landscapes for game
purposes, specifically 1000x1000 maps with a terrain type for each tile.
The result from the above two programs looks better than my ad-hoc
island maker, but there are some problems for my purposes: it needs
smoothing, it's a weird size, and there's no guarantee that the
"islands" won't be right against the map edge even when the DS code is
seeded with zeroes at the corners. I could crop, force the edges down in
some efficient way, and apply smoothing, scale2x, and erosion, maybe. Or
just use fewer, bigger tiles; or even use a genuinely smaller map size.
Thoughts?

Kris
"...Only slightly higher, so we get a two-level effect, with a little
path running down the middle."