Terragen [site not available today] is without doubt the best damn landscape generator I have ever seen. Although the official site's not up, there are a couple of mirror sites from which you can grab the app itself.
My landscapes aren't quite as good as the ones at Planet Terragen, but I'll get there. Next stop: Animations. From memory, there's a fantastic movie at the proper Terragen site -- but as I said, that's not there today.