The gradation is not objectionable IMHO.
Don't like polarizers, most of the time you're at the wrong angle, they just make things worse.
However...over on the pretty blue right hand side, take foreground/background color samples for the lightest and darkest blues. Select only the sky areas. Make a new layer over this image, use the selection to create a mask on that new layer. One the new layer create a gradation with your two sampled blues. Play with the transparency on the gradation. Blur the mask if you need to. Maybe pile up multiple gradations on the gradation layer at slightly different angles at low transparency, maybe slightly modify the shades of blue on each of these. Maybe just borrow a different sky from another photo. In Photoshop, anything is possible.