I'm actually not digging what you've done. You've made it look like a storm is coming. Here's my 3 minutes Lightroom fix up. White balance was way off.. too cold. There is still blueness to the sky, it's not blown out and represents a sunny day at the beach.
Agreed - I only made the change to address comments made before my posting, which was the horizon and that the sky was overexposed that that the OP should have used an ND filter. I simply added a gradient layer in PS to emulate a ND filter to bring the blue back. Like you, I probably spent a full 3 minutes adding it, and never adjusted the Opacity of the layer to reduce the darkness that I added. I was primarily just trying to show that it is very simple to add an ND effect like this in PS if you dont have one - or forgot to use it.
I also didnt make any other color changes (e.g. white balance) which you did - and I do like better than the original.

