Your best bet at the time the shot is taken will be a graduated neutral density filter... a large rectangular filter held in front of the lens in a bracket: half of it clear, half of it about two stops worth of neutral gray. Slide it up or down and turn it as needed to match the horizon line in your shot.
The reason your skies are looking washed out is because they are so much brighter than your foreground and the rest of the scene. The graduated filter balances the exposure.
A standard ND or neutral density filter will simply reduce the light from the entire scene, and your metering system will correct for that... you'll end up right back where you started from.
A polarizer tends to look blotchy or uneven on very wide lenses, because the effect is strongest 90 degrees from the sun and the lens takes in such a wide expanse that it's simply bound to be uneven.
Another approach would be to take two exposures... one for the fore and middleground of the scene, the other for the sky. Then strip the two together in Photoshop. You actually can do something similar by double processing a single RAW file, once for the sky, once for the rest of the scene, and stripping those two images together in PS. Sometimes these are the best technique, such as when you have a very uneven horizon.
