One thing that springs to mind for me in vanilla Minecraft: encountering a cool cave. It might have a mob spawner in there, or a lava pool maybe with some diamonds that will require careful mining, or an "old" mineshaft. The emergence here I guess is that the cave feels "real", with lava in the depths and coal/iron higher up as rewards. I imagine that caves originally were an emergent factor from the world generation, then got their own hard coded cave-specific generation paths added to make something much more playable. Much like rogue-like games that have hard-coded rooms in them that are randomly spread through the dungeon, the caves have hard-coded set-pieces that can join together in new and interesting ways.

Elite is really primitive compared to today's games, but it had a huge galaxy to explore (even if all the systems were essentially the same 1-star-and-planet), then eventually you find out there are 8 such galaxies. It was fun to find good trade routes between the worlds, risk going to a slightly more lawless planet to beef up your credits or ranking. The emergence here would be the fact that the economic type of a planet was dependent on its seed value, and together with other nearby generated planets created "trade routes". These routes were not coded into the game, they emerge as a property of the way the procedural generation works out.

I think the problem with making so much procedural is that it misses the point that the game should be fun to play. What's the game-play difference in having random trees or dependent on sunlight and rain? In the end, they are just a bunch of trees :-P