What I would love to see is persistent map alterations, such as flood / drought, earthquake, volcanic eruption, landslide/avalanche, growing cactuses, toxic rains, torch-explosive underground gas pocket, and so on.
Once you get the point of boredom, these would create new challenges. You would be surprised by the new of topography of the map, instead of knowing the map by heart and what to expect everywhere (which is the case on Navezgane, but also after playing a random map for too long).
Also, I feel like world persistence (a quite costly feature on the programmatic side) is really not leveraged. What's the point of remembering the whole map state when players only build a few bases / mines, destroy only a few buildings and bridges ? With this solution, you would really show what full world memory can bring to the game : an automatically evolving world to which you need adapt (not just popping more Z in the same spot) !
Also, each game would end up being different due to randomness in these events (even more than it was random to find schematics in a16). It's unfortunate how the introduction of skills and scalable Z in a17 gave the game a feeling of linearity that was not there in a16.
There are probably challenges in implementations and balancing, but I feel there are many options available (rare events, quests to trigger them, slowly evolving effects) to balance that in both coding and difficulty.
Last but not least, the apocalyptic nature of these events integrates well in a Z apocalypse lore (god's punishment, alien technology triggering ...)