Even if one concludes that Christianity is Avodah Zarah for non-Jews, it is not clear that most non-Jews are deeply attached to their avodah zarah beliefs, and further more there are Christian groups whose beliefs differ greatly in areas touching the halachic definition of Avodah Zarah. See Rav the contemporary Rabbi Henkin's citation in Bnei Banim 35 of Rabbeinu Yerucham's (1290-1350) description of the non-Jews of his time as "not deeply attached to Avodah Zarah", and the Raavan Rabbi Eliezer ben Natan (''Ra'avan'' of Mainz) (1090-1170) spoke about this as well, and Rav Rabbi Henkin sees in him grounds for distinguishing among the various churches.
It has been noted that in the Maimonides' day and Islamic environment, it was just as dangerous to say that Christianity was not idolatry as it was for the Tosefos to say that it was.
