The Rambam (Machalos Asuros 11) writes that the Christians are plain avoda zora worshippers.
The Noda B’Yehuda writes (YD 148) that it is a common mistake to think that Goyim are not commanded against schituf. The reality is they are. The error, he says, comes from a Rama that says you are allowed to cause a non-Jew to swear to his god, since he is not swearing to an idol but just adding his idol to Hashem, meaning schituf.
But the NB”Y points out that all this means is that the Goy does NOT declare the idol to be a deity in the oath, but the belief itself that a deity shares power with G-d is really idolatry. Only the oath is permitted, since it does not express his real belief.
Other poskim concur with the Noda Beyehuda.
And although there are some poskim who do hold that Goyim are not commanded against schituf, but it doesn’t make a difference anyway, because that only means that the Goyim are not sinning for being idol worshipers, which is between them and Hashem, but as far as we are concerned, we are commanded against schituf, and that makes them idol worshippers to us (Responsa Binyan Tzion I:63).
Christianity is Avoda Zora because they worship a god who impregnates women, and other characteristics such as a trinity that constitutes idolatry as opposed to worshiping the real G-d.
To better understand the issue you may want to distinguish between Christianity as a religion and medieval Gentiles who professed Christianity.
Christianity as a religion was just as much Avoda Zara to the Baalei Tosafos as it was to the Rambam. A simple proof of this is found in Avoda Zara 14b, d”h hatzav, where it is stated that it is forbidden to sell wax to the Goyim (for fear they will make votive candles). The issur is based on the verse “Lifnei Iver lo titen mikhshol” which is understood to mean that a Jew is not permitted to cause another (Jew or Gentile) to sin. We see from this that lighting a votive candle is a sin , i.e. avoda zara, even for a Gentile.
That the Baalei Tosafos allowed business with Goyim on religious
holidays, despite the Mishna to the contrary (2a, d”h asur), does not contradict the above. Rather, they held that Goyim do not take their own (idolatrous) religion seriously enough to offer thanksgiving for the profit they make from such commerce. That is, they made a distinction between the religion as such and its devotees. Because of this many rishonim (Rashi, Rabbenu Tam, etc.) ruled that Gentile wine is not forbidden in benefit (not assur behana’ah)– Goyim today are mostly not priests and do not carry out the mass.
The “proof” that the Baalei Tosafos did not hold that Christianity is avoda zara comes from the statement that Goyim are not commanded to avoid “shituf.” However the commentators from the world of Torah (i.e. Chazon Ish, etc.) [and even from the academic world (like David Berger, etc.)] have proved that this discussion (in Sanhedrin) is relevant only to oath taking (i.e. swearing to Hashem but having somebody else in mind as well), which is the usual meaning of “shituf shem shamayim im davar aher” in the Talmud. Christian worship as carried out in the medieval Catholic Church was regarded as avoda zora, period, for Jew and Gentile alike.