This came up in a discussion about The Big Bang Theory. While Bernadette is a nice character and I like her, she’s no Amy Farrah Fowler. That character has really added a new dimension to the show.
Likewise, Married with Children really improved when Ted McGinley joined the cast as Jefferson D’Arcy. He was the perfect foil for both Marcy & Al.
I also loved Martin Mull as Roseanne’s new boss Leon Carp. He & Roseanne really played off well with one another.
Add your choices, please.
Adding Urkel to Family Matters was a great success. I’ve heard anyway, never watched the show.
Adding Reverend Jim to Taxi was a home run. I liked Simka too.
Game of Thrones: It’s hard to believe at this point that neither Tywin Lannister nor Brienne of Tarth appeared in season 1.
The Office (US): I never liked that British lady, but Erin (the new receptionist) and Holly (Michael’s love interest) were both fantastic additions.
Buffy: Plenty of characters came and went, but Oz, Anya and Tara all joined later than season one and then for at least a while were integral parts of the central gang
Breaking Bad: Neither Saul Goodman nor Mike-the-Cleaner showed up until late season 2.
Kari on MythBusters added a character and a smile that wasn’t evil.
I think Dawn also added a dynamic to Buffy that was welcome.
David Ogden Stiers as Charles Emerson Winchester, Mike Farrell as ]B.J. Hunnicutt, and Harry Morgan as Sherman T. Potter, all in M.A.S.H. all added something to the series. So did semiregulars like Dr. Sidney Freeman.
As has been remarked, Henry Winkler’s character “The Fonz” wasn’t in the pilot for Happy Days, and wasn’t supposed to be a major character in the first season, but he ended up taking over.
Despite not being in the first two pilots, I don’t know if “Bones” McCoy counts as an add on or not. But, without his completing the Holy Trinity, Star Trek TOS would have been very different.
So I’ll throw in 7 of 9 (VOY) for adding new plot opportunities (even if they didn’t really capitalize on the ops).
Frasier, and later, Lilith, added a lot to Cheers. Woody did as well, but I’m not sure if the OP means to include replacement characters as well as added-from-whole-cloth ones. If so, then Christine Sullivan of Night Court deserves a mention as well.
Frasier on Cheers was originally intended to be in just a few episodes as a Sam/Diane plot complication. He lasted 20 years.
The first season of Newhart was kind of bland. After that they added the characters of Stephanie and Michael, and Larry, Daryl and Daryl and the show went to new levels in surreal.
The Mother on How I Met Your Mother was done so well a lot of viewers actually got upset over her fate, despite her only being present in the final season.
I agree with **MASH **ones above.
Barney Miller: Sgt Dietrich
Star Trek: Ensign Chekov (I don’t count Bones, he got there very early)
Northern Exposure: The many part time regulars that were added.
Mary Tyler Moore Show: Added Betty White as Sue Ann Nivens , Georgette not so much.
Best addition ever: Rev Jim to Taxi
Bones- Adding Dr. Sweets (John Francis Daley) added a lot to Booths character.
Supernatural - Adding Misha Barton as Castiel changed a lot on the show.
It’s Always Sunny in Philadelphia took off when Danny Devito joined in Season 2.
is there a difference between an added character (an increase in the number of characters) and a substitute character (a character replaces a dead or retired character that was written out of the script)?
And Gus, who came on even later! 
When Natalie took over from Sharona on Monk. Also when Monk’s psychiatrist Dr. Kroger died and was replaced by Dr. Bell.
Angel: Illyria
She brought a couple of interesting things to the show.
I liked *Star Trek: Deep Space Nine *from the beginning. But when they added Mr. Worf at the beginning of season 4 (I think), it REALLY got good!
Alan Shore showed up in the last season of The Practice, and turned the series completely around.