But even with an infinite landscape, I think you could improve the variety by using a generator at different scopes - if your landscape is just one constant type of terrain, like a field, things will get boring. You might have a wide variety of rivers and trees, but the basic idea is the same. But if you have another generator controlling the terrain type - going between plains, desert, mountains, etc., that would be really interesting. At the small scope, variation in trees and water is still the same level of change, but there is also a larger scope that changes the overall feel at a much larger radius.
Instead of {noise(x,y)>0.5 = desert} let's simulate eons of weather, geological events, floods, and then feed that back into the lore of the game world. Dwarf Fortress is one of the few games I'm aware of that attempts this level of world generation. Unfortunately it's quite impenetrable as a game, due to its complexity.
As for Perlin noise, check out Simplex noise. It's what Perlin designed AFTER Perlin noise. I use 4D Simplex fractals to create my game world which tiles seamlessly when scrolling up/down as well as left/right. And I'm filling the world with random-but-connected cities, factions etc. That's where interesting emergent gameplay comes from.
BTW, I have a few writeups (quite technical) on the correct implementation of Simplex noise on spiralcode.wordpress.com
So, instead of creating infinite worlds I'd like to see a lot more focus on procedurally-generating very interesting finite worlds. For games with a simple 2d tile-based grid, we then don't have to limit ourselves to just crafting noise-based functions -- as we can create the entire world at once. Games like Dwarf Fortress, Spelunky, Nethack, Terraria, etc., all follow this approach, and I'm trying to do the same in my own game, Moonman. So get our your IDEs and start creating house, face, forest, creature, item, and cloud generators. :)