Edit: This is not 1000 generations stuff. This is "crawled from the sea into a perpetually foggy land and evolved as such" stuff. For 1000 generations I'd imagine the main adaption is a resistence to Pneumonia and other illnesses caused by breathing damp cold air.
For a real world example (urban legend?) Kenya is very high up and has a lower oxygen density. So the people there have adapted to have more efficient lungs.
Frog Skin:
Frogs can breath through their skin, at the cost of needing to stay wet or else they suffocate. They are very happy in your misty environment since it means they don't need to stay near a puddle at all times. Your humanoids have a similar slimy skin that lets them absorb oxygen -- not only through their lungs -- but through every part of their body. This leads to greater physical endurance. The lungs are still there as a backup but if the air suddenly dries out they become slow and lethargic.
Outside noses:
Noses are similar to lungs in that they must stay damp to work. That's why the smell tissue for the nose is inside the body. It's also why a dog's nose is damp. But if the air is always damp you could have a big rumpledy-dumpledy (extra surface area) bunch of smelling tissue on the outside of your body.
Reduced Eyesight: Since visibility is so limited their eyesight never developed and so they rely more on smell.