For Bay Area people, there are companies that teach seaweed foraging: what types to look for, where to look, healthy versus "on the toilet all day", etc. Always nice to have another excuse to go to the beach, especially at unusual hours (such as before dawn to catch a low tide).
They might have noticed that eating a little amount of seaweed will prevent illness.
For omega-3 fatty acids, they had much better food sources in bone marrow or in fish (the multicellular algae have very low content of fatty acids; those that are used for omega-3 fatty acid production are unicellular and they are not algae, even if they are named "algae" in advertisements and on labels, because it is believed that something like "straminipiles" would be incomprehensible for laymen; even many scientists misspell "straminipiles" as "stramenopiles", only "Straminipila" is correct Latin).
The vitamins were also abundant in their food, only iodine is deficient in all terrestrial food.
Evolution works through reproduction so any condition that doesn't impact survival until sexual maturity is unlikely to face any evolutionary pressure. Since humans are tribal and took care of their offspring in group settings, survivability after procreation also has little effect.
[1] https://iris.who.int/bitstream/handle/10665/43010/9241592001...
Diseases that impact even just appearance can surely make you less attractive as a mate though. And larger goiters can impede breathing or swallowing. So I'd be suspicious of the idea that we've been significantly deficient in iodine for extended periods of our evolutionary history.
I’d be far more suspicious of applying modern standards of beauty to humans that lived hundreds of thousands of years ago.
Ruminants are more efficient at absorbing nutrients from plant material due their digestive system, and this is how they get iodine in non-coastal areas.
All vertebrates have thyroid glands and there is a very similar organ in marine chordates: https://en.wikipedia.org/wiki/Endostyle. So this is an organ that likely emerged when our biological ancestors still lived in a iodine-rich environment.
Some places still (mostly) don’t. A notable exception (I’m sure there are others but not as well reported) is Israel where iodized salt isn’t a regulatory requirement and not very popular, with (predictable) widespread deficiencies:
https://ijhpr.biomedcentral.com/articles/10.1186/s13584-020-...
https://www.haaretz.com/science-and-health/2017-03-27/ty-art...
https://www.sciencedaily.com/releases/2017/03/170327083438.h...