I must say, I love working with terrain generation. It can take a while (depending mostly on the size of the world you're generating) but it doesn't take long to write, and you can do some really interesting stuff with it.
I wrote a diamond-square (simple fractal) map generator once that did the following:
* Cliff map decides where cliffs, valleys, and sloping terrain go.
* Height map takes influence from cliff map.
* Fertility, temperature maps take into account the height map (lower temperature in high places) but are generally just diamond-square.
* Forestation, terrain texturing, etc. take into account the height map, fertility map, and temperature map all at once.
The end result was something that produced natural-looking, interesting maps quite suitable for use in RTS games. Not every map was playable, but for my purposes (where the player would be able to preview the map before jumping in, to make sure it was acceptable) it was sufficient. (I'm currently tweaking it to generate a fun map for a third-person RPG, which is a whole additional kettle of fish...)
The problem, of course, comes when trying to ensure that the maps are well-designed for play: that nobody starts in an enclosed valley with no way out; that nobody starts on the top of a mountain with no flat area to build in; that all the resources are evenly distributed; that paths are possible between all players (if, for example, you have no ships, you can't start people on separate islands!); etc. It's much harder to create a map that plays well than one that looks good.
Basically, you need to make sure that every single map that comes out of the thing is completely playable. 'Cause if someone - anyone - starts their first game and gets presented with a one-tile islet and no way forwards, you've created an angry customer. If it's a reviewer, it's even worse - that bad map in all likelihood goes into the game score, and you lose sales.
I also remember that the Anno series tended to do the same thing as you have - the maps were, officially, randomized; but the individual islands were designed, and finite in number. I'm not entirely sure which approach I prefer as, while the randomized approach offers constant variation, the preset approach made for some very interesting, unique places to build in.
As a sidenote, one approach I find conceptually interesting is asymmetry in map design. Let every player have access to essential resources, but perhaps split essential resources into several categories and just make sure every player has access to at least one. If one person has horses and one person has iron, the one can have a strong cavalry while the other has strong swordsmen, and the one with cavalry may try to conquer one of the swordsman-player's cities to secure the iron as well. This is the way the Civilization series tends to do it, particularly in later periods with oil and aluminum, and it has almost entirely positive effects on the gameplay structure. An easy way to link this in with map generation is by making resources dependent on climate, thereby eliminating the repetitive nature of play noted by Vandenburg.
And that's my twenty-two cents.
