This week's Parsha, ראה , has fifty four laws in it. These laws helped shape Jewish life when they were to enter Eretz Yisrael.
A strong point that is made in the Parsha is that the land is not able to tolerate idol worship. There is a commandment to destroy all forms of עבודה זרה in order to purify the land. However, we are to be careful not to destroy any of our holy places where the name of G-d is upon it. This includes the prohibition to destroy a synagogue.
The של״ה הקודש quotes the Talmud in Chullin 13 that says that Gentiles outside of Israel are not considered idol worshippers. This is because the rest of the world is ruled by negative forces. Chutz L'aretz is defined as טומאת העמים, the impurity of the nations. The Rabbis assigned Chutz L'aretz a degree of טומאה that one needed to purify himself for whenever one left Israel. Because of all of this, idol worship outside of Israel was not such a contradiction.
This also helps us understand why the Rambam felt that it was preferable for a non-Jew to practice Christianity or the Islamic religion, than no religion at all. He no doubt was speaking of חוץ לארץ where the negative forces are present. It was better that they believe in something rather than believe in nothing. And as long as it was חוץ לארץ, it wasn't really עבודה זרה.
All of this kind of makes one wonder why a Jew would choose to live anywhere but Israel.