Going back to the OP’s first reference (Shakespeare in Love), I would nominate Antony Sher as Doctor Moth (“Apothecary / Alchemist / Astrologer / Priest of Psyche / Interpreter of Dreams”). His reactions when Will describes being “humbled . . . in the act of love” are priceless.
“I am here to help.”
“Interesting . . . most interesting.”
Or for that matter, jack nickelson in the original version
I think most of the cast of The Big Lebowski was a cameo
His counterpart, Ben Afleck, was a basketball player in Buffy the Vampire Slayer.
Oh, boy, I get to nominate John Turturro as the Hispanic pedophile bowler in The Big Lebowski.
“Nobody fucks with the Jesus, man.”
Reaching way back, Elisha Cook, Jr. as the young thug repeatedly abused by Humphrey Bogart in The Maltese Falcon.
And Peter Lorre in what seems like a whole bunch of films from the '40s.
This made me think of the Richard Widmark role in the original Victor Mature version of Kiss Of Death (recently remangled by David Caruso, Nicolas Cage, and Samuel L. Jackson, among others) where he pushes the old gal in the wheelchair down the stairs. I recall the role as small except for that bit and the patented Widmark smirk/giggle/whinny.
Wilford Brimley in Absence of Malice
How many minutes is Marlon Brando’s screentime in Apocolypse Now? I would guess maybe 15.
Robert Duvall as well.
Wow, thanks for the info Equipoise!
Jane Adams aka the naked chick from The Anniversary Party is not the droid we’re looking for- although I do LOVE her, she was the reason I went to see Orange County so she might be enough to get me to see Last Holiday as well. I know from the trailer that Jane Adams plays the “best friend” role in New Orleans.
As near as I can guess from a bit of imdb-ing, I think the actress we’re talking about is Lucie Vondrácková (another pic). She’s credited as a character named Marie. I don’t know if that makes her our talented little Hotel receptionist or not (I still haven’t seen the movie) but the second pic I linked to kinda matches my memory of the actress appearing in the trailer.
The three greatest “Ohmigod, they are going to be stars” movies are:
1.American Graffiti
2.The Lords of Flatbush
3. Uncommon Women…and Others
Off the wall one, but the Rock Giant in The Neverending Story:
“These hands look so strong…” 
From Clue:
“This… is… your singing telegram!”
Blam!
Thud.
Stanley Tucci as Frank Nitti in Road To Perdition.
Raymond Burr as Montgomery Clift’s prosecutor in Place in The Sun. The role got Burr an audition for the Hamilton Burger role in Perry Mason,but Burr made it clear that he wanted the lead or nothing.
Billy Connolly in The Boondock Saints. He has about 5 minutes of screen time but manages to be one of most badass movie hitmen ever in that 5 minutes.
He also has a bit part as Sean Penn’s brother in Dead Man Walking. And was a theater usher in True Romance, but was left on the editing room floor.
I wonder if Ahnold had any say in Paxton’s considerably larger part in True Lies …
A good bet, at any rate. There’s an archived interview with Paxton on Fresh Air that goes into how much “dues paying” Paxton went through before things started breaking his way. He and Billy Bob have some common history, too.
One would get the strong impression that these early-on connections last a long time. Burt Reynolds and Ned Beatty. John Wayne and Ward Bond (and maybe a dozen others). Might make for a fun thread of its own. 
Actually, I think the director might have had more of a say than the star… Paxton & Cameron worked together in:
Aliens
Ghosts of the Abyss
Terminator
Titanic
True Lies
Good point. IMDB allows one to check for such pairings and it might make for some fun searching to see which pairs of actor/actor, actor/director, director/writer, director/composer, etc., have the most collaborations.
It wouldn’t surprise me if there are cliques that span more than two categories. John Ford comes to mind. Hitchcock had his own stable of regulars. Blake Edwards had a loyal group.
Somebody needs to get a new thread going on this!
