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.
I remember an experimental game from years ago that was essentially a dungeon crawler without the er, crawling part. That is, there was no 'space', similar to the beginning phase of this game. It was actually quite fun, and seems like it could impart some ideas for expansion in this game.