Bruce,
Your end result here is certainly very good.
I don't really have too many tips to offer, other than try to get a good exposure when you take the shot. The skies tend to be under-exposed because there are so many other bright areas in the frame, so the dark areas can get noisy.
I learned to stay away from using "auto levels" as it seemed to bring up noise. I may have not been using it correctly, but I had seen others saying the same thing in forums.
you can also use the blur tool passing it over the sky area, but that's really no different than what you are already doing.
If you are getting the big blocky stuff in the sky, noise reduction many times won't smooth it out, as it's really not noise.
If you are going after a particular scene that you really want badly, and are willing to spend some time on it, use a tripod, and take a 3 shot burst. You may or may not want to vary the EV during the burst. Then layer the shots in Photoshop. Since the noise is randon, the layered result will tend to have the noise smoothed out. You can't just use multiple layers of the same image, as the noise will line up layer to layer. Maybe process them using HDR?
Just a few thoughts (and no real solutions).
