Age of Empires II: Age of Kings
One of the things that made the Age of Empires series stand out against the other RTS games of the era was the procedurally generated maps.
Where many of its contemporaries came with a fixed set of skirmish maps to memorize, Age of Empires had map generators. The first game, with its expansion, had eight map types, while Age of Kings came with over a dozen map generators. Two dozen with The Conquerors expansion.
Since the maps were random, you couldn’t memorize where things were, transforming the chess-like opening books of a typical RTS to something that required a bit more adaptation and attention as the players scouted the map to discover the basic shape of the terrain. Learning where the resources are becomes as important as observing what your opponents are up to.
Age of Kings also opened up the map scripting system to modders, letting anyone code up their own random map in the somewhat idiosyncratic custom map generation script. Ensemble Studios released their own series of custom map generators online for free, giving players new content in one of the early effective uses of the Internet to enhance a game. Combined with the map editor, this gave players a huge amount of new content and helped cement its online community.
It’s worth considering releasing new generator as bonus content. While each individual generator probably took quite a bit of development time, on the development time to player content ratio it did pretty well. Plus, the new maps could afford to be more experimental or unbalanced, since anyone who used them was already looking for something different.