I really like Terragen, but IMHO, Bryce is the clear choice. If you invest about an hour in learning how to alter the 2 or 3 dozen preset skies, you can do just about anything (and not worry about the Terragen $99 license if you want to go commercial). While I still have much to learn, these have gotten good reviews (and 9000 downloads so far), and they take about 2 minutes each:
http://www.alsip.net/gamedev/media/skybox/index.html
or:
http://www.vaxwar.com/gamedev/media/index.asp
I'm average about 1 word a week on a tutorial I promised months ago, but here's where I learned everything I know (also has a 3DS Max tutorial):
http://www.gamasutra.com/features/19981023/bell_01.htm
gamasutra requires a free registration to see the tuts, but I can honestly say I've not received a single spam email after giving my email address. (and I love their site).