On my commute today I had the idea and desire for a new way to play KaC. In several RTS games, there is a type of game sometimes called "Nomad." Whatever any particular game calls it, the idea is that you start with your starting villagers/workers spaced out over an unexplored map, and must have them convene and find an advantageous position to found your nation/kingdom.

I thought this would work well with the additional caveat that you would begin with a ship of some kind, and would be forced to build an Outpost building no more than 10-20 tiles away from the ocean, to help immerse the idea of coming across this island to found a kingdom. Perhaps eventually the Keep would be "unlocked" after a certain number of subjects move to the kingdom.

As an aside, I think this would work hand in hand too with finding some way to place multiple outposts on the map, even on one large island, so that you can run multiple "towns" independent of one another, with their own resources, taxation rates, and populations.