Christina,
You have a tendency that you want a photograph to display the colors as you remember them in a scene when you photographed it. When capturing scenes that have a lot of haze, that presents a particular quandary for you: the presence of the haze not only is a color that you do not want to replicate in the photo, the haze also limits the dynamic range in a way that you don't want to replicate.
So, you have only two choices now that you have understandably decided that you don't like haze: either don't take the picture or alter it so significantly during post-processing that it no longer resembles the colors or the dynamic range that you experienced.
To demonstrate my point that relatively effective images can be made that bear no resemblance to the colors or dynamic range that you experienced, consider the monochrome version of your first image minus the top layer of clouds. I made this image far too quickly, as you can see by the lack of detail in a few areas. Even so, hopefully it helps support my point that you need to get away from the requirement in all situations that the photo replicates the scene.
