Truth be told, I would have take 2 exposures and done what you have said. However, I was... how do you say it. Quite high, really. During the taking of the shot. But yeah, agreed completely. I hope you still have the RAW file, you can lower the exposure in there and make the sky look all pretty and that's all you need.
For your nature photos, the ones including the sky, I'd suggest taking 2 exposures of the same scene. A normal exposure and one with 2-4 stops under exposure so then you can use the underexposed image as a layermask for the normal exposed image. Know what I mean? Open the normal exposed image in photoshop, then drag in the under exposed image on top, add a layer mask on the top layer, use the gradient tool and add a gradient going up to down so the image blends together.
See how my photoshop skills are doing. You can get a render from planetrenders.net, I have a account there so I can get any image you find. The max size for a signature is 500x250, here's the order form: Size: Render: Text (if any): Anything else: Example: I'll keep adding examples, I guess.
Think I might start up fishing again. I've been away from my higher skills for a while and only been raising lower skills. I'll be fishing at barbarian village in w1 if anyone wants to join.