I exclude the Simpsons because in addition to being on the air for 20+ years it’s hard to top Thomas Pynchon. Johnny Carson on David Letterman was probably the absolute ultimate, though if you went for sitcoms only his appearance on Newhart was unexpected.
Sticking to sitcoms, I remember being very surprised when Burt Reynolds guest starred on THE GOLDEN GIRLS back when he was still considered a movie star (but was testing the waters of TV). Huge ovation. Bob Hope was also a guest star but it was clearly filmed separately and incorporated; IIRC he didn’t interact with the regular cast.
Speaking of animations, Gore Vidal’s voice cameo on Family Guy was a shock. (He was later on THE SIMPSONS, which I’ll mention because I’ve already used him in the OP;).)
Michael J. Fox walked into the scene in Scrubs, giving me just enough time to say “hey! I know that guy from somewhere!” before he walked off screen again. He walked back on screen, seemed to get frustrated, and walked off yet again. He walked on screen for a third time and, apparently satisfied, continued into the hospital.
His obsessive/compulsive character was probably the best guest star showing I can remember. As a matter of fact, Scrubs featured other fantastic guest star performances by actors I don’t usually consider great, like Colin Farrel.
I thought Richard Dawkins in Doctor Who was a nice touch, given that he’s married to Lalla Ward, an ex-Time Lady who was previously married to Tom Baker: Ward was introduced to Dawkins by Douglas Adams, who was a writer on the show.
Jackie Mason as a guest voice on Spongebob Squarepants (I also love the appearances of Ernest Borgnine and Tim Conway)
Jerry Mathers and Rocki Rhoades on Married With Children
Tammy Fay Bakker’s appearance on the Drew Carrey Show was hilarious
Robert Culp and Louis Gossett Jr. in Half Life 2*
Robert Culp on The Cosby Show
The Candian sitcom Corner Gas has had quite a few surprising guest appearances, including:
Prime Minister Paul Martin
Prime Minister Steven Harper
Former Governor General Adrienne Clarkson
The band The Tragically Hip
Kiefer Sutherland, and his mom Shirley Douglas (in separate episodes).
Duane “Dog” Chapman and his wife
Mike Holmes from Holmes on Homes
One time Vanessa Del Rio, the porn star, appeared on NYPD Blue as herself. It kind of surprised me – this was back before porn had mainstreamed, and the detectives pretty much treated her like any celebrity with a problem. It was interesting.
I was thinking John Wayne on Maud. I didn’t know about the *Laugh In *appearance.
I would vote for Suzanne Pleshette on the finale of Newhart though as **Thalion ** posted.
Didn’t see that, but Costello’s appearance as an annoying coffeehouse musician on “Frasier” was an entertaining surprise.
ETA: At the time I hadn’t seen much of the new (old) Elvis and knew him as his old (young) self, so I kept saying, “Is that… No. Yes! Is it?” to myself.