Coltrane
Ben Webster
Paul Desmond (with Brubeck)
Stan Getz (Getz & Gilberto - he doesn’t get much better)
If we can include pop/rock hits, then “Just the Way You Are” by Billy Joel, “Born To Run” by Bruce Springsteen and the E Street Band, and “The Sad Cafe” by the Eagles all contain excellent sax solos by Phil Woods, Clarence Clemons, and David Sanborn, respectively. Another good song featuring the sax is "Who Can It be Now? by Men At Work, with saxophone by Greg Ham.
Just to be clear, Coltrane never stopped playing tenor, and it is as a tenor player that he is primarily known (though his innovations on soprano are incredible too).
What I came in to mention. That whole album, not just the single, will open up his ears to some possibilities.
If you can find “Baker Street” by Gerry Rafferty (big hit in the 70’s), the whole song is built around a sax riff.
Classic Funk - Tower of Power (full horns with lots of tenor & bari sax)
Any of the classic R&B from the 60’s - all going to have good backup sax work
Jazz Greats - Gerry Mulligan, Ben Webster, Benny Carter, Scott Hamilton, Art Pepper,
Oops - hit an early reply my mistake
Classic Funk - Tower of Power (full horns with lots of tenor & bari sax)
Any of the classic R&B from the 60’s - all going to have good backup sax work
Jazz Greats - Gerry Mulligan, Ben Webster, Benny Carter, Scott Hamilton, Art Pepper, The Byrd, Cannonball Adderly
Spyro Gyra (late 70’s - early 80’s), Sadao Watanabe, David Sanborn
Marcia Ball (latest Live CD has some great backup sax work)
Dr. John - Creole Moon (beautiful work on the title cut)
Marshall Tucker Band (early CD’s)
Early Tom Waits
Dave Matthews Band for a variety of saxes, though mostly on the lower end of things. (Baritone and bass and others I couldn’t name)
Branford Marsalis has played with any number of bands in the last couple of decades. On Sting’s first (two) solo albums he was part of the band, not a guest. Also worth finding are “Eyes Of The World” with the Grateful Dead (on Without A Net) and “Pickin’ Up The Pieces” with Widespread Panic (which I can’t seem to find at the moment).
The Rolling Stones had a pretty good sax player back in the day, as did Traffic. 
Loggins and Messina have a song called “Angry Eyes” that has the sax player switching back and forth between sax and flute IIRC. (And that is my year’s quota for Loggins and Messina recomendations.)
“Us And Them” was gonna be my Pink Floyd suggestion, rather than “Money”, but that’s just me.
Lots of Steely Dan songs have sax parts or you could go straight to the source and play him something from the Crusaders ( I like " Stomp and Buck Dance" from their Southern Comfort CD, but the whole album is good.)
That’s probably a whole CD’s worth just from (mostly) the 70’s.
Hey, about about some classical stuff? Hindemith used the saxophone a fair amount. There’s a good list of classical recordings here.
I’m sure you meant to type “Bird”, as in Charlie Parker the saxist, not “The Byrd”, as in Charlie Byrd the guitarist. I can’t believe I didn’t include Sonny Rollins in the list of jazz sax greats.
:smack: Ever since we named our middle son Bryan, I find myself using the y instead of the i…
Good suggestions all, but what about Johnny Hodges, the alto sax player with Duke Ellington, famous for his sinuous sound on ballads? For sheer sax loveliness, try “Daydream” from the album “And His Mother Called Him Bill”, and “Star-Crossed Lovers” from “Such Sweet Thunder”.
He wasn’t just a ballad player, though - some really excellent, swinging stuff on the albums “Back To Back” and “Side By Side”. Plus countless other recordings of his - slow, fast, everything.
thanks all, will have to do some sorting.
“Avalon” by Roxy Music is lush and sexy as hell with the sax work, but might not be exciting enough to inspire a teenager.
How about some of the swing revival bands of the late ‘90s? That scene has come and gone, but the music is still fun and awesome. Royal Crown Revue’s Mugzy’s Move, Big Bad Voodoo Daddy’s self-titled album, the Cherry Poppin’ Daddies’ Zoot Suit Riot, and the Brian Setzer Orchestra’s Guitar Slinger all have plenty of wild and crazy horn parts and sweet sax solos, jump blues and big band swing influence, and punk rock energy. You can probably get all those CDs really cheap now on eBay or the Amazon Marketplace, since the fad is so long over.
Tom Waits also has great saxophone players backing him up on the jazzy, beat poetry-inspired albums Small Change and Nighthawks at the Diner.