Noach and Shem were alive during the time of Avraham, and I know midrashim say he lived in their house for some time learning about Hashem, but how come the whole world was practicing polytheism, when there were witnesses to monotheism, and they would have passed it down generations? How could people have “come up” with Avodah Zarah, when monotheism should have been brought down through the generations?
Hi and welcome to Mi Yodeya. The short answer is that people who never spoke to Hashem aren't necessarily going to believe others who claim they did. However, given that it was indeed so generationally close to Adam, I still agree it needs more explanation and so does the Rambam in the first halachot of Avodah Zara in Mishneh Torah.
To summarise, first realise that this happened over several steps, over a long time. As modern social media informs us, even in an age of unlimited access to information, people are still so easily convinced to totally get behind a philosophy, on the tiniest shreds of evidence and convincing. So the following is totally, utterly reasonable:
Step 1: Well intentioned-mistakes. People made a great mistake and decided that Hashem would want us to honour His honoured stars and planets. They began to offer sacrifices to the stars1.
Step 2: Lies about Hashem. After time passed, people arose and told everyone that this is what Hashem wanted, they heard so from Him (false prophets).
Step 3: Lies about Idols. Deceitful people then took it further and said that the idols themselves spoke to them, and told them that they wish to be worshipped, in such and such ways. This step, when it spread throughout the whole world, was what made everyone forget God completely.
Step 4: Threats. As we see with what happened to Avraham in the court of Nimrod, they eventually would threaten those who refused to worship the idols with execution. Fear is a great tool at preventing truth from taking hold in a person's heart.
I strongly recommend learning the entire Rambam I linked and quoted, chapter 1.
1 what was the mistake? The mistake was that the stars and planets are likened to Hashem's ministers (which He of course honoured), but humans are Hashem's children. It's a corruption for the Prince to honour the minister. Hashem is offended when we go to one of His ministers to commune with Him. As His children, we should go direct to Him.