Whether it be to add new flavor to a show, replace a character, or to try to save a dying show, lots of producers have added character to a show for one reason or another.
So who is your favorite character that was added to a show?
For me, Lennie Brisco, Law and Order, nqa.
Ezri Dax from Star Trek: Deep Space Nine and Andrew from Buffy the Vampire Slayer are the two that jump immediately to mind.
Rebecca Howe on Cheers or Butters on South Park
Aunt Esther and Grady on Sanford & Son (while they seem as if they were there all the time, they didn’t come on board until well after the first season)
Winchester from MASH. Burns was a complete buffoon - everything he ever said or did was meant to be wrong and stupid, except that he must have been a halfway decent doctor to be there. Winchester was a foil for Hawk and BJ who was quite intelligent and articulate, won battles of wits with the “heroes” occasionally, and was given several good qualities.
Butters was there from day one, he just didn’t talk :).
Kryten on Red Dwarf, who joined the crew on a permanent basis in Series 3. The earlier shows were good, but he added a lot to the mix.
Spike on Buffy. At least, up until about mid-Season 5. 
Recurring character of a chainsmoking, snarky, genuinely dangerous vampire? Cool. Permanent character of a moody, passive-aggressive, whitewashed exposition fairy? Not so much.
In the Whedon vein, I fell madly in love with both Gunn and later Illyria on Angel.
Not a permanent character, but Daphne’s ne’er-do-well brother Simon on Frasier was one of the most spectacular television characters in recent memory. LaPaglia won an Emmy for the role, didn’t he?
Seven of Nine, from Star Trek: Voyager.
HA!
Bruce Boxleitner as Capt. Sherdan on Babylon 5. Not the greatest actor, perhaps, but exactly the right actor for the role. Before he came aboard, the series didn’t really come together for me. He made it click.
Practically the entire supporting “cast” of the Simpsons: while they only really provided background in the initial series, as they were developed as characters they shifted a lot of the immediate focus off the Simpsons themselves, and gave the principals any number of distinct characters to interact with - as the series developed further, the Simpsons often became peripheral to the antics of the “supporting” characters, with stalwarts such as Mr Burns and Krusty providing much of the comic meat, and relatively minor characters such as Troy McClure enjoying episodes of their own; this prevented {or delayed…} the antics of the Simpsons themselves becoming stale or repetitive.
On preview, that reads incredibly pompously: blame Askia; I’ve just come out of his"superheroes" thread, and I’m still in mock serious mode.
How about Popeye (the Sailor Man)?
He was an incidental character to Elzie Segar’s Thimble Theater. t the time the stars were the Oyl family, notably Olive and her brother Castor (along with her father Cole and her later-named mom Nana). Olive’s boyfriend at the time was Ham Gravy. Castor hired a wizened, one-eyed sailor to get them over to an island, and he took over the strip.
As much as I hate to admit it, I think adding/replacing Sharona with Natalie on **MONK ** has injected new life to the show. I hated the last seaon with Sharona, but I find this season compelling.
Adding Mork to Happy Days was the sort of inspiration that only comes along once every century.
Although I loved Coach on Cheers I felt that Woody was a wonderful addition. I also liked Lillith.
I also felt Col. Potter was an excellent addition to MASH.
I also felt that Festus on Gunsmoke* was a good and entertaining replacement for Chester Goode.
I felt some of the Dr. Who’s were good and some were…but there were so many but Lelia (was that her name? - the cave girl type) she was nice to look at and she did something besides just scream and get captured.
Seven of Nine, Charles Wincester as previously mentioned.
Also Kay Carter-Shepley (Lily Tomlin) saved the last two season of “Murphy Brown” from mediocrity.
“Please… Mozart.”
He has a wonderful voice.
Word! Woody is not only my pick for best character addition, but one of my favorite characters off all time in general.
Of course, if Arrested Development survives a few more seasons, George Michael may give him a run for his money. 
Well if you want to go really old school then it would be Donald Duck. (I have a problem expressing my anger, I enjoy watching someone who does not have that problem)
A little more recently it would be Batgirl on the classic Batman TV show.
Checkov, of course and I liked the role he played on Babylon 5 as well.
Steve Thomas on ‘This Old House’. Anyone was better than Bob ‘God, don’t give him a hammer!’ Vila.
I love how Disco Stu, originally invented for a throwaway line (“Disco Stu doesn’t need to advertise!”) became a recurring character.
My vote: Chiana on Farscape. Didn’t like her much at first, but she developed into a very complex and nuanced character.