I kinda think the opposite is true. It's people who live in cities who join PETA. Country folk get acclimatized to commoditizing animals.
I'd like to see a summary of the evidence that many Native Americans actually prayed for forgiveness to animal spirits. There's been a lot of retrospective "reframing" of Native American culture in the past 100 years--go to a pow-wow today and an earnest Native American elder may tell you stories about their great respect for the Earth, but I don't find these stories in 17th thru 19th-century accounts. Praying for forgiveness makes a great story, but you usually hear about it from somebody like James Fenimore Cooper rather than in an ethnographic account. Do contemporary accounts from the Amazon say that tribespeople there do that?
(Regarding the reliability of contemporary Native American accounts: Once I was researching the Cree Indians, and I read an account, circa 1900, by a Cree, boasting that their written language was their own invention and went back generations before the white man came. The next thing I read was an account from around 1860 of a white missionary who had recently learned Cree and invented the written script for it. I may possibly be confusing the Cree with Ojibway, but it was the same language in both stories.)
I'm not aware of any Western religion that says cruelty to animals is a sin. Individual interpretations, maybe, but I'm pretty sure you won't find a word about it in the whole of the Bible. The Anglican church was fine with bear-baiting. I don't think the Catholic church complained about vivisection.
And it's certainly true that tribal cultures gave zero or negative weight to the well-being of competing tribes. Utilitarianism is tricky to apply when you have to periodically kill your neighbors to survive.
In any case, indigenous cultures aren't the ones complaining that utilitarianism leads to utility monsters. The people who've made those arguments do have their own preferred utility monsters.
I'm not aware of any Western religion that says cruelty to animals is a sin.
FWIW I'll provide some institutional references:
The current Catechism of the Catholic Church section 2418 reads, in part: "It is contrary to human dignity to cause animals to suffer or die needlessly." The 1908 Catholic Encyclopedia goes into more detail.
I also searched for statements by the largest Protestant denominations. I found nothing by the EKD. The SBC doesn't take official positions but the Humane Society publishes a PDF presenting Baptist thinking that is ...
When someone complains that utilitarianism1 leads to the dust speck paradox or the trolley-car problem, I tell them that's a feature, not a bug. I'm not ready to say that respecting the utility monster is also a feature of utilitarianism, but it is what most people everywhere have always done. A model that doesn't allow for utility monsters can't model human behavior, and certainly shouldn't provoke indignant responses from philosophers who keep right on respecting their own utility monsters.
The utility monster is a creature that is somehow more capable of experiencing pleasure (or positive utility) than all others combined. Most people consider sacrificing everyone else's small utilities for the benefits of this monster to be repugnant.
Let's suppose the utility monster is a utility monster because it has a more highly-developed brain capable of making finer discriminations, higher-level abstractions, and more associations than all the lesser minds around it. Does that make it less repugnant? (If so, I lose you here. I invite you to post a comment explaining why utility-monster-by-smartness is an exception.) Suppose we have one utility monster and one million others. Everything we do, we do for the one utility monster. Repugnant?
Multiply by nine billion. We now have nine billion utility monsters and 9x1015 others. Still repugnant?
Yet these same enlightened, democratic societies whose philosophers decry the utility monster give approximately zero weight to the well-being of non-humans. We might try not to drive a species extinct, but when contemplating a new hydroelectric dam, nobody adds up the disutility to all the squirrels in the valley to be flooded.
If you believe the utility monster is a problem with utilitarianism, how do you take into account the well-being of squirrels? How about ants? Worms? Bacteria? You've gone to 1015 others just with ants.2 Maybe 1020 with nematodes.
"But humans are different!" our anti-utilitarian complains. "They're so much more intelligent and emotionally complex than nematodes that it would be repugnant to wipe out all humans to save any number of nematodes."
Well, that's what a real utility monster looks like.
The same people who believe this then turn around and say there's a problem with utilitarianism because (when unpacked into a plausible real-life example) it might kill all the nematodes to save one human. Given their beliefs, they should complain about the opposite "problem": For a sufficient number of nematodes, an instantiation of utilitarianism might say not to kill all the nematodes to save one human.
1. I use the term in a very general way, meaning any action selection system that uses a utility function—which in practice means any rational, deterministic action selection system in which action preferences are well-ordered.
2. This recent attempt to estimate the number of different living beings of different kinds gives some numbers. The web has many pages claiming there are 1015 ants, but I haven't found a citation of any original source.