Pig is an industrial band probably most known for sharing members with kmfdm.
So when they do a cover of Head Like a Hole, why not make it a jazzy/swing-type cover?
Luther Wright and the Wrongs did a great Bluegrass cover of the entire album “The Wall,” looks like someone combined all three parts of the title song and uploaded it here.
The Dirtbombs, covering Stevie Wonder’s Livin’ for the City.
Awesome!
The Civil Wars take on Billie Jean. Even the Michael Jackson fans like this one.
Billy Corgan - Smashing Pumpkins - Landslide by Fleetwood Mac
Butch Walker and the Black Widows - In Bloom by Nirvana
I could go on forever baby, I LOVE successful covers.
Eva Cassidy’s version of Time After Time.
Better than the original:
William Shatner - Common People
I’m going to have to disagree with this one. My complaint with over 90% of the covers of that song is that the singer just tries to turn it into a display of their awesome vocal range and/or quirks. Never mind the meaning of the lyrics of the song.
They also did “'Til There Was You”, a song written in 1957 for The Music Man.
God, yes. And going the other way, Live doing I Walk the Line.
This guy does an amazing cover of LMFAO’s “Sexy and I Know It”.
Mandy Patikin- Somewhere Over The Rainbow http://www.youtube.com/watch?v=CswSMdQ2TDE
Hindu Love Gods- (Warren Zevon and REM minus Stipe) Raspberry Beret http://www.youtube.com/watch?v=61PgHobvCYs
Prince, Tom Petty, Steve Winwood, Jeff Lynne and others -While My Guitar Gently Weeps http://www.youtube.com/watch?v=6SFNW5F8K9Y Check out Prince at about the 4 minute mark.
Here’s the opposite
This is the original version of Tiffany’s I Think Were Alone Now.
Amen brother! That’s why I’ve come to hate Over the Rainbow. Same thing with Etta James “At Last”. It’s gotten to the point where I can’t even stand the original now. But here’s a cover that nobody can touch. Liquid Soul’s version of Dizzy Gillespie’s Salt Peanuts.
I’ve got his appearance with Ben Folds and Joe Jackson on…I think it was Conan. Fantastic stuff
Well Dolly *is *Miley’s godmother…
My 3 year old loves Miley’s cover version. I hope I’m not setting her up to be a country singer.
Oh yes, I forgot about that one! It was on . . . With the Beatles, I think? Their early albums always had a few covers, most of which were very good - I’ve always liked having someone listen to “All You Need is Love,” “Can’t Buy Me Love,” etc, etc, and then play “Money” for them. 
In the spirit of the OP’s “Holy shit, ____ covered _____!!??” I present a very atypically sedate Nina Hagen, singing “Ave Maria.” It’s almost SFW!
Another one that always puts a smile on my face, Danielle Dax’s short but rockin’ sweet cover of “Blue Christmas”
Not in the Holy Shit! category in that it wasn’t unexpected since she’s a huge fan, but this is my go-to normal-people cover. I was actually there (my husband shot the video) and it was as mesmerizing live as it still is to me today. Based on the Comments, it’s not just me. Really!
I’ll give you strange, but I’m not on board with catchy. 
This one’s a little different: Petra Haden covers the Theme from Psycho.
Relevant Cracked Article. I agree with most of what he said about both Johnny Cash’s Hurt and William Shatner’s Common People. Mostly that they brought something that the original lacked. My only complaint is that he fails to acknowledge Joe Jackson’s contribution doing the actual singing on Common People.