My suggestion is that, in addition to the usual goodie huts and autogenerated terrain, there should be "Areas of Interest" plopped down in places (either randomly or places that seem applicable to them).

If anyone's played Torchlight, you'll know that their maps are hundreds of connected "pieces" that've been slotted together. They were designed to be able to link up, instead of just having randomly generated maps. This is a similar concept to what I'm suggesting, except these areas should just be places / islands or whatever put down into the game.

They'd basically be giant goodie huts / monster dens, spawning (preferably low level) monsters into the world to act as an annoyance. They should be worth breaking into, though.

Any questions / comments?