Orlando Bloom was a victim on Midsomer Murders before LotR and Pirates, and Clare Holman had two different roles on the same show before she became Dr Hobson on Lewis (though I don’t know how unknown she really was at the time).
Also, Milla Jovovich as one of the seniors who bully the freshman girls with ketchup and mustard in the beginning.
Pre-talk show, Conan O’Brien was an extra in several SNL skits:
In Zoolander, you have the then little known Vince Vaughn and Judah Friedlander playing Ben Stiller’s brothers.
Another famous movie chock full of future stars: The Outsiders (1983).
Ralph Macchio (a year before the Karate Kid)
Tom Cruise (Risky Business released later the same year)
Patrick Swayze (a year before Red Dawn)
Rob Lowe (two years before St. Elmo’s Fire)
Emilio Estevez (a year before Repo Men)
Dianne Lane (hmm, can’t really tell what her breakout role was)
Sofia Coppola (credited as Sofie Coppola)
Apparently, the “famous names” that the move was built around were C. Thomas Howell (who?) and Matt Dillion, who had achieved fame in E.T. and My Bodyguard, respectively.
Heh I think I’m getting good at this, just think of movies that have a large cast of kids or teens, there’s usually tons of future famous people in there.
Dead Poet’s Society, 1989
Robert Sean Leonard
Ethan Hawk
Josh Charles
The pilot for “Charlie’s Angels” had an interesting what if changes weren’t made. Charlie was supposed to have two male assistants: Bosley (David Doyle) and Scott Woodville played by David Ogden Stiers. But although the pilot was successful ratings-wise, it was felt Stiers’s character was too severe and they could have more fun with the jovial Bosley. They probably figured they could save on salary to spend it on more important things for the show’s success: tiny bikinis and hair swtylists. Stier’s got the better of the deal as a year later he was cast as Major Winchester on “MAS*H”. Also appearing in the episode is Tommy Lee Jones, not his first role, but early in his career. Jaclyn Smith remembers taking Jones’s hand and it was shaking because of nervousness.
oh for heaven’s sake. It was A Little Romance (1979). Co-starring w/ Olivier.
Heh I would have guessed “Must Love Dogs.” 
As a younger kid he played a younger kid in The Larry Sanders Show.
I, Claudius —Captain Luc Picard as a disgusted general of Tiberius in the porno gift scene
In the pilot for Eight is Enough, oldest son David Bradford was played by a pre-Star Wars Mark Hamill.
I cannot see Ray Liotta in anything without thinking of the soap Another World’s Joey Perini.
I was rewatching *Firefly *on blu-ray the other day and in one of the episodes (Ariel?) it shows a flashback or memory of a much younger Simon and River Tam at home with their parents. I’ve watched the whole series multiple times, but this time that boy playing young Simon looked familiar. I looked up Zac Efron’s imdb page and, sure enough, that was him.
He’s not an actor, but this clip of2 year old Tiger Woods showing his golf swing on the Mike Douglas show is just so damn cute.
I saw this clip when he won the Master’s, and remembered seeing it when it originally aired!
I saw the 1979 “Dating Game” ep with PeeWee Herman as Bachelor #2. I had no idea who he was at the time, and it would be several years before I’d see him again, but he definitely left an impression.
Brad Pitt’s first professional gig was as a high school basketball player on the soap Another World.
The 1955 movie Blackboard Jungle featured Jamie Farr (credit as Jameel Farah}, Vic Morrow and Sidney Poiiter playing high school students.
One of her fellow Fly Girls is Dancing with the Stars judge Carrie Ann Inaba.
He played Sejanus.
Stewart can also be spotted in Excalibur and the 1984 version of Dune in his pre-Star Trek days.
He was in Apocalypse Now several years before Deathwish 2.
Note for the person who mentioned Pee-wee’s Playhouse that it was well after both the movies mentioned and amidst a host of other movies that arguably made him a celebrity. In other words, I think he qualifies as famous once he hits the Pee-wee’s Playhouse era.
Edit: My bad, I thought I had read the whole thread and obviously not since Apocalypse Now was mentioned already.
George Clooney was in both “Facts of Life” and “Roseanne.”