S. Epatha Merkerson, Lt. VanBuren on Law and Order, started off playing the mail lady on Pee Wee’s Playhouse.
In his early days of acting, Michael Jeter (Eduard Delacroix in The Green Mile) was Mr. Noodle on Sesame Street.
And of course, the cream of the crop, Morgan Freeman hosted PBS’s Electric Comapny.
These are the only three I can think of, but there have to be more. So, come on, folks, what well-known actors started out on children’s shows?
Michael Keaton pulled the Trolley and ran Picture Picture on “Mister Rogers”. And I believe had a part where he played one of the Zuccinni Brothers in the Land of Make Believe.
And Laurence Fishburn (Cowboy Carl) and Phil Hartman used to be on “Pee-Wee’s Playhouse” as well.
Emilio Delgado and Sonia Manzano both began on Sesame Street and have played other characters since.
One nitpick: Michael Jeter played Mr. Noodle’s Brother Mr. Noodle toward the end of his life. He had a long career before then.
Robin
I did not know that.
I knew that but had forgotten.
You are, of course, absolutely correct; you have fought ignorance well today, grasshopper. 
To pick another nit:
Michael did a lot of things at WQED, which, like most PBS stations, uses the same technical staffers on all of their local productions, so he began his career behind the scenes at Mr. Rogers and a host of other shows as well.
Jeremy Irons got his big break on Play Away. So did Tony “Baldric” Robinson.
Didn’t Britney and Justin start out as mouseketeers? Not that either of them are actors, of course.
She was never a “star” or even a regular, but actress Holly Robinson Peete occasionally appeared on “Sesame Street” as a little girl, back when her father, Matt Robinson, was playing Gordon.
Wasn’t Benicio Del Toro also on Pee Wee’s Playhouse? IMDb doesn’t seem to know about it, if so.
Irene Cara was also on Electric Company.
Lynne Thigpen was Chief on Where in the World Is Carmen Sandiego?.
Also Christina.
Long time soap-opera star Don Hastings got his start as the Video Ranger on Captain Video.
True, but she had been working in film since 1973 so she didn’t “start off” on a children’s show.
The show “Kids Incorporated” started the careers of a lot of younger celebrities, including Jennifer Love Hewitt, Eric Balfour (formerly of “Six Feet Under” and the late, unlamented “Hawaii”), Stacy Ferguson (aka “Fergie” from the hiphop group Black Eyed Peas), Mario Lopez (better known as Slater on “Saved by the Bell”) and the single-monikered singers Martika and Shanice.
Mike Myers started out on a UK kids’ TV show called The Wide Awake Club. I used to watch him.
Most of the cast of Monty Python, got together on a kid’s show called Do Not Adjust Your Set.
Actor David Jason was also in the cast.
Keri Russell, too.
TeaElle stole my Kids, Inc. post. So yeah, what she said.
She snuck in while you were sleeping; if you’re going to sleep during the day, you should really lock your door first. 
Don’t forget Annette Funicello. Several of her Mickey Mouse Club co-stars — Cheryl Holdridge, Tommy Cole, Bobby Burgess, Cubby O’Brien, Sherry Alberoni, Sharon Baird, Lonnie Burr, Darlene Gillespie, Don Grady and Johnny Crawford, for example – also continued to perform on TV, in music and in the movies.
Did he host it, or just play some roles like ‘Easy Reader’?
Stockard Channing started on Sesame Street. The Number Victim or something like that.