I think that the majority of H&H players would like some kind of oceanic or large-scale sea terrain features. However, creating a realistic world generator is not easy task. So, I have what I think would be a very straightforward compromise:
I've based this system off of these assumptions of your current system:
- You have two stages of map generation.
- These are:
- - Basic drawing, which places blobs of terrain like we are familiar with. There is a mathematical formula that draws these shapes, and there may be different formulas for some terrain types, such as drawing rivers in linear shapes and forests in blobs.
- - Implied drawing, which finds parts of terrain such as coastlines and adds things like sand beaches and deep water areas away from shore.
My suggestion is, again, very simple. All you need to do is add a step between the Basic drawing and the Implied drawing that will draw deep water in the inverse of the blob generator! In other words, rather than pasting cut-out paper shapes on the map, cut holes in an empty ocean map and put that on top of your basic map.
Of course, the "holes" that you cut would have to be much larger than normal terrain features, but that should be trivial.
Then you can run the Implied drawing step which adds beaches where appropriate, maybe it adds cliffs that tend to follow coastlines, and fixes little bugs line one-pixel islands, and you're done.
I can't promise that this will make the game world realistic, but it would make it more diverse, and allow for at least a little enlightenment-era age of sail exploration.