As an atheist, I generally don’t have much use for Christian (or whatever) rock. But there are some religious songs that are really fantastic. What are your faves? To keep this thread from getting too gunked up, let’s ignore songs from JCS and Godspell, as that would be like shooting Jesus fish in a barrel.
My personal favorites:
Jesus is Just Alright (Doobie Brothers)
My Sweet Lord (George Harrison)
That’s my favorite. Also Amazing Grace.
“Oh, Lord, Won’t You Buy Me A Mercedes Benz?”
“Drop Kick Me, Jesus, Through The Goal Posts Of Life”
“Plastic Jesus”
Okay, for real:
Old School:
“Will The Circle Be Unbroken?”
Old, Old School:
“A Mighty Fortress Is Our God”
St. Louis School:
“Gather Us In”
“Gift of Finest Wheat”
“One Bread, One Body”
“Though The Mountains May Fall”
“Be Not Afraid”
“On Eagle’s Wings”
I’ll admit that, as a Catholic school kid in the 70s and 80s, I was RAISED on St. Louis Jesuit hymns, and I have the 10 years of liturgical guitar experience to prove it…
Josh Turner’s Long Black Train. The video (YouTube link) is a bit OTT, but the song is catchy, if you like country music.
I had no idea about the St. Louis Jesuits. All my favorites are from them, apparently, but I didn’t know where they came from.
After two years of Montessori, 12 years of Catholic School, and a lot of Mass attendance, my favorites are:
Here I Am, Lord
Be Not Afraid
Wake From Your Sleep
City of God
Also, Let There Be Peace on Earth, which it appears is not by the St. Louis Jesuits.
Dear God by XTC
The Cross (Prince)
I Found Love (Lone Justice)
I think some Big Star songs might qualify but I can’t name them of the top of my head.
IMHO you can’t do better than The Battle Hymn of the Republic
“Mine eyes have seen the glory of the coming of the Lord:
He is trampling out the vintage where the grapes of wrath are stored;
He hath loosed the fateful lightning of His terrible swift sword:
His truth is marching on.”
It’s like god is Jules from Pulp Fiction.
For catchy music I’ll have to go Norman Greenbaum’s Spirit in the Sky.
Personal Jesus - either the Depeche Mode or the Johnny Cash version is great.
Spirit in the Sky - Norman Greenbaum
Why Me Lord? - Johnny Cash
There’s a new one, and it’s fairly obscure, but gorgeous. Bryn Terfel (the opera singer) and Rhys Meirion (another opera singer) do a version of Psalm 23 in Welsh.* The album is Benedictus, available from Amazon. I wish I could find a link to the sound file online (a friend of mine has the album). This from someone who doesn’t normally find religion or opera or Classical music very compelling.
On a completely different note (ha!) in a different genre, Dolly Parton’s “He’s Alive” was always strangely moving for me. I think it’s just the emotion in her voice: she’s clearly a believer.
PS: I went to high school with Norman Greenbaum’s son Jethro, who is very smart. Not that it’s relevant.
JSB’s Jesu, Joy of Man’s Desiring. More for the oboe than anything else.
Oh, and Jesus Built My Hotrod - not so much religious, but definitely inspired… 
There are many but here is one that might be overlooked - “Jesus Wept” by Ralph McTell
http://http://www.amazon.com/Sand-Your-Shoes-Ralph-McTell/dp/B000001BBT
Here’s a sample of the lyric:…
"Then he saw two armies marching and he heard their crucifixes
Reduced to superstitious muted jangling round their necks
And he heard his name intoned as they interred their companion,
And that’s why Jesus wept.
Then he thought about his mother and the stories she had told him,
Who’d filled his dreams with angels, put voices in his head
Then the scent of pine trees made him think of dear old Joseph,
And that’s why Jesus wept."
Tom Waits - “Chocolate Jesus”
Okay, maybe not…
Ummm…I’m pretty sure George was singing about Lord Krishna (listen to the chorus singing “Hare Krishna, Krishna Krishna” etc)
I said religious songs, not Christian songs. Krshna is a religion.
It does make me wonder where all the Jainist songs are, though.
Also by Depeche Mode: Blasphemous Rumors.
The OP’s choices are obviously the first two I thought of, though and I love them both. I would also say Imagine, but that is more spiritual and anti-religious.
I was also quite entertained by The Devil Went Down to Georgia. He was in a bind ‘cause he was way behind and he was willin’ to make a deal. 
Shoulda known we’d be on the same page. Even though I am not religious, I love The Cross by Prince.
And the Big Star song you are thinking of is **The Ballad of El Goodo **- where Alex Chilton says “…and at my side is God - and there ain’t no one who’s gonna turn me 'round”. I love that song.