See Ramban to Breishit/Genesis 34:13 that Gentiles are held responsible for their idol worship.
See also Rambam (Maimonides) Hilchot Melachim (Laws of Kings) chapter 8 (in the Mossad Harav Kook edition) halacha 9 where he also agrees.
Tag-MehirTzedek stated:
I think their were some Rishonim (Mayaritz Hayot comes to mind- or actually an Aharon) who said that a gentile who breaks one of the 7 Noahide laws is evil except when it comes to idol worship. I would need to double check this, but I think perhaps this is where it comes from.
Although the name you quoted is not spelled correctly but I think I know who you are referring to and he is not a Rishon. I also did not hear him say exactly what you said.
Although I didn't read his words inside, but I was told he follows the minority and I stress the minority opinion, that Gentiles outside the land of Israel, who believe in "Shituf" are not violating idolatry.
The majority say they are.
Issue #2
Tag-MehirTzedek, the quote you brought from Chullin 13B is not meant in the context to exempt them entirely from the sin of idolatry.
The Gemara in Chullin goes on to explain (quote from the Soncino English Translation)
R. ‘Ukba b. Hama said: The rule applies to the matter of accepting sacrifices
from them.
Some based on this Gemara, also relax certain halachic restrictions against doing business with the idol worshipers.
I currently don't have the time to go into detail.