There couple interesting threads in Rogue Temple forums about generating flags and symbols and about Ultima Ratio Regum which uses procedural content generation beyond the usual 20+ level dungeon filled with monsters and items. Dwarf Fortress is another example of a game that does something like this.
This all got me thinking that it would be nice to do something that has not been done countless of times before. Of course coming up with a thing like that is hard, but things that are hard are often things that are worth doing. And I can just get started by doing something, that is not done as often as level generation.
Dwarf Fortress has system that sometimes generates a monster that is dangerous and hard to kill and throws it against your fortress. These monsters have procedurally generated abilities and appearance and can sometimes be quite nasty. Since I’m planning to write end bosses into the game, some of them could be generated procedurally. That would give players something new to fight with, instead of serving the same canned boss fight every time. If boss fights belong to game with instant death is another matter though.
History of the world is another part which I could enhance with content generation. The main points are written down, but I could fill in the blanks and let them vary between games. These could come in form of engravings, statues and other similar things (sort of what Dwarf Fortress already does).