According to the Mishnah, there were places in Israel where Jews sold behemot dakot – sheep and goats to their non-Jewish neighbors, while in other places they did not. Behemot gasot – large cattle – however, were not sold to non-Jews in any place.
The Gemara explains that the source for these restrictions is not because they were worried about pagan idol worship, rather they stem from other halakhic concerns. Behemot gasot were used for field work that would be done on Shabbatas well as during the week. Since Jews are obligated to ensure that their animals do not work on Shabbat, they cannot lend their animals or rent them to non-Jews if they will be used on Shabbat. Since we are concerned that people would mistake purchase for renting or lending, even selling such animals was prohibited.
The reason given for restricting the sale of behemot dakot is a different one. The Gemara explains that bestiality was commonplace among some of the non-Jews who lived in Israel in the time of the Mishnah. Since sexual relations with animals is forbidden to non-Jews as one of the seven Noachide laws, it would be forbidden for a Jew to aid and abet such behavior. Understandably, in places where such behavior was unheard of among the non-Jews, sale of these animals was permitted.
The Talmud Yerushalmi offers a different approach, suggesting that behemot dakot cannot be sold to non-Jews since that takes away from them the ability to be involved in mitzvot (e.g. sacrificing the first-born or offering the first shearings to the kohen). Ultimately, this suggestion is rejected by the Yerushalmi, since then it could be argued that even produce should not be sold to non-Jews, since mitzvot like tithes would be lost to the crops. Nevertheless, the Me’iri writes that such reasoning should be considered and that we need to distinguish between common animals that can be sold out of concern for the livelihood of the Jewish cattlemen, and those that are less common.