The original image [ISO => 400, F11, 1/320 seconds, -1/3 EV] looks washed out, may be because of bright day light overhead. In GIMP, if I apply Tools => Color Tools => Levels => Auto, the picture improves quite a bit. What sort of post-processing, either in Photoshop or Gimp or any other image processing tool, can I do to improve the washed out image even more?
Recent Adobe Lightroom (& Camera RAW) versions have a feature called "dehaze", which is designed specifically for this sort of thing. It's a little more advanced than just levels adjustment. I've had mixed success with it - sometimes it looks good, sometimes the resulting image has excessively muddy shadows. I believe it works a bit like auto levels but doesn't treat the whole image the same. So in your case it would affect the mountains more strongly than the foreground that already has more contrast.
Add a sky. I just quickly tried with Paint.Net (not the most advanced tool ever) and current sky is selected perfectly by the wand mode. Then steal a nice looking sky from another of your shot, put into a layer behind, and blend.