Okay, well that worked WAY better than I expected. Only took me about half an hour to convert a (slice of a) heightmap into a depth-map (a linked-list of 2D arrays, each containing "walkable" water or rock).
Looks much improved over my spikey, organically-grown maps and also means (and this is going to be incredibly useful) I can pre-generate massive maps (e.g. 32K on a side) and load regions in chunks.
Pretty chuffed at that. 😀