Not like Amy Grant’s “Baby Baby” (ugh).
Songs for which the unsuspecting being from another planet could conceivably think the song was worship material, from a religion that the aliens had not discovered yet.
First example: Queen’s “Fat Bottomed Girls”.
(Many less-worthy religions have existed!) 
Ooooo yes I like it
I originally meant the lyrics praising or worshipping, and you’ve found one where the music is what sounds religious, but sure.
I guess that “Son of a bitch, gimme a drink” song sounds pretty gospel-y.
Probably songs that sound gospel style or spiritual style but aren’t religious are fairly common, I don’t know.
Springsteen and the E Street Band’s live version of “Light of Day,” with the extended witnessing to the Church of Rock and Roll in the middle. That’ll make anyone a Believer!
Pinball Wizard
Flashlight
Whip It
Paper Roses
Afternoon Delight
As you listed a Queen song in your OP, I’ll further nominate Somebody to Love, for its gospel feel. And, for that matter, one could interpret the lyrics as a search for a deity to worship.
I suppose Personal Jesus is out?
Notice, also, that it follows the classic chorus-verse-chorus-chorus-chorus-chorus convention of popular songwriting.
I’m thinking “Na Na Hey Hey Kiss Him Goodbye.” I can imagine the report back to Mars:
"Earthlings gather in a huge house of worship to watch their priests; who, wearing holy garb, attempt to defeat priests from another house of worship, in order to establish some sort of dominance in the religious hierarchy. To encourage their priests, adherents of the local house will often chant something that sounds nonsensical, but does culminate in the Earth word, “Goodbye.”
Hahaha
Me like
I never thought of that but wish I had
What’s the closest thing to a god, without being one? Well, I figure it’s a superhero; and what’s the closest thing to a superhero? I figure it’s Flash Gordon, who’ll save every one of us: every man, every woman, every child…
“We gotta get out of this place” The Animals.
Spirit In The Sky
The Church of The Fuzzy Guitar.“Now You’re In Heaven” by Julian Lennon (actually about sex)
If they think ZZ Top’s “Sharp Dressed Man” is a religious song, they may think Michael B. Jordan, Chadwick Boseman, and Daniel Kaluuya are our gods.
I’m ok with that.
The Candy Man–a reality warper capable of transforming anything into confections.
Queen again. “We Will Rock You”. After all, pretty much everyone within earshot when it plays performs a ritualized, rhythmic action throughout the song. Obviously a religious ritual.
Paradise By The Dashboard Light would be one of several songs suggesting the role of cars in religion.
