One of the older versions of Bryce was released for free. That's pretty decent for terrains, especially islands with a really badass sunset in the background. Dunno how it would be for a large world. You'd have to plant trees and rocks yourself.

I'm partial to Terragen, which also has a free version. Instead of the usual grid with textures, you tell it where in the world certain colors appear. You can do this by height or slope, I think. It sounds primitive, but the results are stunning once you get good at it. Obviously the learning curve is high. This wouldn't do trees and such either FWIW.