Rene Auberjonois at the Shakespeare Theatre in Moliere’s The Imaginary Invalid
Harry Hamlin in Henry V at DC’s Shakespeare in the Park
Bebe Neuwirth and Victor Garber in Damn Yankees
Kelsey Grammer in La Cage Aux Folles
Simon Jones and Joan Collins in Private Lives
Jonathan Silverman in Brighton Beach Memoirs
Not chronologically:
Gilda Radner in… something;
The older brother from Weeds in Spring Awakening;
John Ritter and Henry Winkler in *The Dinner Party *(I think);
Philip Seymour Hoffman and John C. Reilly in True West;
Alan Ruck and Richard Kind in The Producers;
I’m sure there are more.
Alan Rickman and Jerry O’Connell in Seminar.
We got to meet both of them afterward, too. Very cool.
Zero Mostel in a touring company of Fiddler on the Roof when I was a very little kid. I barely remember it.
Patrick Stewart in Yonadab on the London stage, two years before he was cast as Capt. Picard. He was very good as a jovial, backslapping, politically-savvy King David.
Colm Wilkinson and the original cast of Les Miserables in London, also in late 1985. Fantastic show. One of the very few times in my life when I’ve leapt to my feet to applaud at the end.
Alec Guiness and Edward Hermann in the Cold War-era drama A Walk in the Woods. Very good show. Spoke to them both briefly at the stage door afterwards, too. Guiness was a little annoyed to be asked by a German fan to sign glossies of Obi-Wan Kenobi ("You’re just going to turn around and sell them, aren’t you?).
Jonathan Pryce in The Seagull. He played the conflicted writer Trigorin, as I had in a college production a few months earlier. Oh, man, how I wished I’d seen his take on it first - he was simply masterful. When I saw him in the audience for another play a few weeks later, I worked up the courage to introduce myself and tell him that. He actually seemed bashful!
Tim Curry in She Stoops to Conquer. Probably the funniest stage comedy I’ve ever seen, largely due to Curry’s manic scenery chewing. Also saw him years later in Spamalot, which I actually found kind of disappointing.
Kate Mulgrew in her one-woman Katharine Hepburn show. Not bad, but not awesome either.
George Hamilton in La Cage Aux Folles. Ditto.
Avery Brooks (a lot of people in this thread have seen him!) in a one-man show about Paul Robeson. Pretty good.
Jeremy Brett and Edward Hardwicke in The Secret of Sherlock Holmes, reprising their TV roles. Sheer bliss for a Holmes fan like me.
Patrick Stewart in A Christmas Carol
Christian Slater in One Flew Over the Cuckoo’s Nest
Kevin Spacey in Philadelphia Story, Moon for the Misbegotten (also with Colm Meaney) and Speed the Plow (also with Jeff Goldblum)
Jeff Goldblum in Prisoner of Second Avenue
Daniel Radcliffe in Equus
Woody Harrelson in Night of the Iguana
Lauren Ambrose (from Six Feet Under) in Buried Child
Kathleen Turner in Who’s Afraid of Virginia Woolf?
Ken Stott (Rebus) in A View from the Bridge
Tim Curry in Spamalot
Ewan McGregor and Jane Krakowski in Guys and Dolls
I saw both Kristen Chenoweth and Idina Menzel in the San Francisco test run of Wicked. Both went on to TV and movies. Both were electric, owning the stage with a charisma I’ve never seen.
Richard Burton in Camelot, mid 80s revival. Good, but he was not as impressive as I thought he would be.
Yul Brynner in The King and I, same time period. This was after he was diagnosed with lung cancer. The only obvious sign, though, was cutting short the long notes at the end of each line in “Is A Puzzlement!”
Zero Mostel in Fiddler on the Roof, mid 70s.
I just saw:
Russell Brand
Eric Idle
Billy Connolly
Eddie Izzard
Tracey Ullman
Tim Curry
in What About Dick?
*Way *too many to count or remember. I see over 50 Broadway/Off-Broadway shows each year. Already this year I’ve seen:
Matthew Broderick in Nice Work if You Can Get It
Blair Underwood in A Streetcar Named Desire
Raul Esparza in Leap of Faith
Tom Wopat in Pipe Dream
Ben Daniels & Jennifer Tilly in Don’t Dress For Dinner
Linda Lavin in The Lyons
Kevin Spacey in Richard III
And in the next two weeks I will be seeing:
Topher Grace in Lonely I’m Not
Jim Parsons in Harvey
Tate Donovan in Medieval Play
In 2011 I saw:
Zachary Quinto in Angels In America
Nathan Lane & Bebe Newirth in The Addams Family
Andre Braugher in The Whipping Man
Jennifer Carpenter in Gruesome Playground Injuries
Billy Crudup in Arcadia
Daniel Radcliffe & John Laroquette in How To Succeed In Business…
Dana Ivey in The Importance of Being Earnest
Ellen Barkin, Lee Pace & Jim Parsons in The Normal Heart
Justin Bartha in All New People
Frank Langella in Man and Boy
Marlo Thomas & Steve Guttenberg in Relatively Speaking
Bernadette Peters in Follies
Alan Rickman & Jerry O’Connell in Seminar
Mekhi Phifer & Dule Hill in Stick Fly
Carla Gugino & Rosemary Harris in The Road to Mecca
Harry Connick Jr in On A Clear Day You Can See Forever
Ditto - same play. Swoozie Kurtz was also in it.
Glenn Close in Crucifer of Blood.
Joanne Worley (of Laugh-In fame) in the Mad Show before she was on and in a local theater production after.
René Auberjonois in City of Angels
Raul Julia in Two Gentlemen of Verona in Central Park
Penn & Teller (hey, they were in a movie)
Loretta Swit in The Mystery of Edwin Drood
Derek Jacobi in the play about Turing, Breaking the Code
Adam West - on a set, so I’m not sure it counts
One of the early Sesame Street adults in the original Anything Goes
and of course my daughter. 
I saw Lea Thompson as Sally Bowles in a touring production of Cabaret.
And Skid Row’s Sebastian Bach as Jesus in Jesus Christ Superstar.
Daniel Radcliffe in How To Succeed In Business Without Really Trying
Patrick Stewart in Macbeth
Cate Blanchett in Plenty
Kelsey Grammer in Macbeth
When I was in school:
[ul]
[li]Andy Gibb in Joseph and the Amazing Technicolor Dreamcoat[/li][li]Harry Hamlin in Hamlet. Must have been 1983 or '84. At the time, I only knew him from Clash of the Titans. My friend sitting next to me couldn’t have cared less. All I remember about the play was her sighing, “his pants are sooo tight.”[/li][/ul]
More recently:
[ul]
[li]William Peterson in Dublin Carol at The Steppenwolf[/li][li]Michael McKeaon in Superior Donuts, also at The Steppenwolf[/li][li]Lorraine Bracco in The Graduate[/li][li]John Mahoney in The Seafarer at The Steppenwolf and in Better Late, by Larry Gelbart[/li][/ul]
Can you tell I live near The Steppenwolf? 
Speaking of - I’ll add the name Jon Michael Hill. He had a role in the short-lived TV series Detroit 1-8-7, and it looks like he’s got a recurring part in Eastbound and Down. I mention him because I don’t see any reason why this kid shouldn’t be a big star some day (except for the fact that he’s kind of short, but that never stopped Tom Cruise). We saw him in Superior Donuts (for which he was nominated for a Tony when it moved to Broadway); The Tempest, where played Ariel; and Kafka On The Shore, which play I did not understand at all. He’s a very good actor, can sing, dance, do some acrobatics, and is just one of the most dynamic personalities I’ve ever seen on a stage. Seriously, he should be a huge giant star, so I’m putting this out there as my I-saw-him-when… moment.
Jealous!
Even more jealous! Brendan Coyle was in that!
Was that with John Larroquette?
I saw Leslie Nielsen in his one-man Clarence Darrow show. He was brilliant!
I saw Ashley Judd (Maggie), Jason Patric (Brick), Ned Beatty (Big Daddy), and Margo Martindale (Big Mama) in Cat on a Hot Tin Roof on Broadway. Ned Beatty was especially good!
Far, far too many to list. The one that stands out the most is Irene Ryan in Pippin, singing her swan song No Time At All
My contributions seem inadequate, considering some of these listed here - but for someone out in the sticks of Iowa, I do have a few to add.
My wife and I saw Carol Burnett in her Show where she tells some backstage stories and then takes questions from the audience. Plus, we were in the second row!
I saw Joe Mantegna and Peter Falk in Glengarry Glen Ross back in the 80s. Some college friends and I actually walked past Falk on the sidewalk earlier that day, but I didn’t see him until we were already past.
Don’t know if Cherry Jones counts, as she is better known for her theatre work, but she’s been on TV (24, Awake). We saw her onstage in Doubt.
Nathan Lane and Bebe Neuwirth in the Chicago tryout of The Addams Family. They reworked the script before it went to Broadway, so, yeah …
Also just remembered:
Juliet Stevenson in Troilus and Cressida, early in her career. She was very good.
Roger Rees in Love’s Labours Lost. He had sort of a sometimes-manic tragicomic grace in the role that really stuck with me.
Ben Kingsley in the title role of Othello, playing him more historically Arab than contemporary black (he was a Moor, after all). He did it with a tragic dignity that packed a real dramatic punch.
I’m curious, was he wearing his hair piece? I have seen pictures of him in uniform late in his career and he went bald when he was doing his Air Force thing.
I saw Graham Chapman give a lecture at my college.
Hank Azaria, Davis Hyde Pierce and Sara Ramirez in Spamalot (Tim Curry was off that day)
Brent Spiner and Pat Hingle in 1776
Nathan Lane and Matthew Broderick in The Producers