I'm working on a game with a procedurally generated world. Ideally, I'd like to generate landscapes as beautiful as Minecraft's worlds are. Minecraft has chasms, and waterfalls, and mountains, and rolling hills, and oceans, etc. But as this is going to be a top-down (actually 3/4 perspective) game, I don't believe most of that is possible. The main reason being how hard it is to try and represent height in this perspective. Zelda: A Link to the Past created the illusion of height well, but this would be very hard to recreate procedurally, and also introduces some problems such as the fact that the tallest structures have to be at the top of the map.
So, I'd like to know some techniques to make landscapes interesting in a top-down format without having to fake a 3rd dimension. (You cannot create or destroy terrain in this game, so that gives us a little more flexibility.)
EDIT: To make things a little more clear, I'm trying to avoid worlds with features that require a 3rd dimension. For example, I can't really have rolling hills or mountains. What landscape features could be added that don't require faking a 3rd dimension? One answer could be to add rivers, but that's an obvious one.