It's a tough problem because imposing goals seems to imbue a game with meaning, yet imposing goals runs counter to the very freedom that draws people to sandbox games. Minecraft gets by with a massive amount of complex, emergent gameplay arising from how the blocks interact with the environment and each other, but still faces that "but what now?" sense (of existential angst?) over time. "Where is this all going? What's it all for?" seems difficult to avoid.
Ramping difficulty (ala Dwarf Fortress) could help but might seal late stage gameplay behind a competency wall.
Some ideas:
* Steal minecraft's blocks, but make them people generating effects you have to deal with: Merchants are great for taxes, but merchants selling too much ale convert laborers to drunkards; introducing priests lowers drunkenness by increasing virtue, but causes people to be less happy and productive; troubadours make people happier, but make priests angry; etc. etc.
The game could introduce a wide range of "people blocks" with different interactions, even maybe changing behavior based on time (priests become less effective over time as population grows), population density (troubadours form an art district, creating new trade goods) and proximity (labor district next to docks amplifies productivity, but increases smuggling crime)
* Player defined disruptive randomizers (within a range): Let players specify before game a range of events with percentage chances of happening. Similar in spirit to SimCity & spawning tornadoes or earthquakes, but more integrated into the game along the lines of difficulty. Better if you can throw a bunch in a big list, some delayed by time (so the barbarian invasions never happening in the first 30 min of playing).
* Rulebreakers: You understand the rules and are bored? What happens when someone opens the ancient tomb or pandora's box or invents a new technology which upends them? Houses built from wood from the mystical forest no longer burn, but attract a procedurally defined threat (orcs one game, bandits another, cultists the next); metal mined from a cursed mine procedurally affects gameplay, in one game allowing construction of boats that are twice as swift but mysteriously cause fish to die (disaster for an island nation), in another making it possible to build greater buildings which sometimes attract ghosts! (I'd suggest making several items have multiple, overlapping effects, by the way, so that effects like fish kills can't easily be just the result of cursed metal, but also farming practices or an evil, aquaphobic cult)
Rulebreakers & people blocks actually might work well together: Imagine gems which attract the best artisans, which make nobles happy, which are (initially unknown) from a cursed mine, which then turns nobles quarrellous and greedy.
A variant of all this could be more of a hybrid game, by the way, like one which funnels gameplay variation and rule changes through a "choose your own adventure" style overlay similar to King of Dragon Pass. The replay value would be phenomenal if the "story" were more loose and procedurally generated, maybe with one game pitting players against a rising threat while another accentuates settling conflict between fractious populations while still a third is more of a murder mystery involving a powerful traitor creating chaotic and disruptive effects. Much tougher to implement and a nightmare for balance, but experimental players would probably love it!
A big advantage of such a hybrid game would be that it has an ending, which drives that satisfying internal sense of completion and sidesteps "growth as if you're a cancer" ethos I think people find unappealing over time.