As acknowledged in the question, Judaism only requires that non-jews keep the seven Noachide laws (plus some miscellaneous laws which are beyond the scope of this answer). Seeing as the first of these is the prohibition against idolatry, it is clear that belief in any polytheistic religion is definitely a problem. That the prohibition extends to belief in addition to action can be seen from the Rambam in Hilchot Melachim 9:2.
What about atheism? Is atheism less problematic?
Jews (according to most classic opinions) have an explicit mitzvah to believe in God. There is no such mitzvah amongst the seven Noachide laws. Only the prohibition against idolatry. In the past, I inferred from this that there would be no problem with a non-jew being atheist. After all, one can be atheist and keep all of the seven Noachide laws. The problem with this is a halacha found in the Rambam, Hilchot Melachim 8:11, which states that a non-jew who keeps the seven Noachide laws because of his own moral calculations instead of because of God's commanding them doesn't get full credit for them (note that there are two variants of this halacha. See the Frankel ed. The above point stands according to both though). We thus see that the behaviour of a non-jew who doesn't believe in God is deficient regardless of how good his behaviour is. Apparently then, belief in God is some sort of prerequisite to the seven Noachide laws. This would also explain why the Rambam mentions this halacha immediately before listing the seven Noachide laws and their various details.
It appears then that atheism would also be a problem for non-jews, albeit a less severe one than polytheism.
What about Christianity* which professes to be monotheistic? The classic sources generally think that Christianity is idolatrous, for example, the Rambam explicitly says so in Hilchot Ma'achalot Assurot 11:7 (see the Franked ed. for the uncensored version) as well as in other places. There is however an often quoted Tosofot to Sanhedrin 63b which states that it is permissible to force a christian to make an oath with the name of God because the christian is only "associating" (shituf) God with his idolatrous beliefs and this is permissible for non-jews to do. There is significant discussion regarding whether Tosofot means that shituf is generally permitted for non-jews or only in the context of making oaths. To summarise then, according to one school of thought, Christianity is as problematic as any polytheistic religion while according to others, there may be no problem depending on how you interpret the aforementioned Tosofot.
Even though the question explicitly excluded Islam, it seems appropriate to deal with it here anyway because it will give us an insight into other religions in general. Classically, Islam has been assumed to not be idolatrous. This can for example be seen in the previously mentioned Rambam, Hilchot Ma'achalot Assurot 11:7. This however only addresses one side of the issue. From a theological perspective, Islam is apparently not idolatrous. Does this make it into an acceptable belief system for non-jews? The answer is unequivocally no. See the Rambam in Hilchot Melachim 10:9 where he explicitly brings a prohibition for non-jews to create their own religions to serve God. In his language - אין מניחין אותן לחדש דת ולעשות מצות לעצמן מדעתן - or in english - "we do not allow them to create a religion or to create mitzvot for themselves based on their opinions". As such, assuming that Muhammed wasn't actually a prophet of God, it turns out that subscribing to Islam and in fact any non-jewish religion would also be problematic for non-jews.
To summarise, from best to worst, we have the following types of belief in God for non-jews:
- Belief in God as described by Judaism (i.e. singular, omnipotent, omniscient, etc.) without subscribing to another religion
- Belief in God as described by a non-jewish genuinely monotheistic religion such as Islam.
- Belief in God as described by Christianity according to some opinions
- Polytheism (and Christianity according to other opinions)
(Note: There may be some room to argue for swapping the order of 3 and 4)
*If I am not mistaken, different denominations of Christianity can have very different beliefs about the divinity of Jesus and other potentially idolatrous beliefs. I'm not familiar with any classic sources which bother to distinguish between the denominations though so I have no way of categorising which denominations are less problematic and which are more.