Adding more locations on the map, procedurally generated minimazes for caves and cities, and either throwing more things/requirements/distance between village and space ship, or even crashing with that spaceship on another planet and exploring that.. until you find another spaceship, and so on :D
Maybe you could have live competition between villages on other worlds? For example, if you and I start at the same time, we can each see the number of villagers of the other person and houses, etc. built so far.
