Diceman:
The black lady was the Public Defender in the first season (not counting the pilot episode); her name was Liz. Billie was the name of the second season’s Public Defender, she was white and blonde with a thick “Noo Yawk” accent, and it was she that Christine most directly replaced.
Roz was a great character, but of the female bailiffs, I always thought Selma’s deadpan delivery made her the best.
She was played by Ellen Foley, who is also a professional singer. She sang the duet with Meat Loaf on “Paradise by the Dashboard Light” on the “Bat Out of Hell” album.
I’d say that Beau Bridges’ Gen. Landry was a better replacement for Don Davis’ Gen. Hammond than Mitchell was as a replacement for O’Neill.
I think the Farscape connection was a bit much for me; I couldn’t see Browder as anything but Crichton in charge of SG-1, and never really did figure out why Claudia Black was on board.
OK, I guess I got Liz & Billie conflated. I don’t really remember Billie then, just Liz.
Dark Shadows didn’t really take off until Barnabas Collins was added.
Can I add a character that basically did a 180 and it improved the show a lot?
Logan Echolls on Veronica Mars. His character started off as a complete a**hole, he even hosted boxing matches between homeless men for goodness sake!
Then, everyone noticed that the two actors had a ton of chemistry, so they had to go about redeeming him and getting the two together.
Both Taub and Thirteen brought some added dimensions to House, particularly in that both were just as broken as House himself and had no firm superior ground to stand on. Taub in particular wrestled believably with his philandering demon, tending to fall just when we believed he had it in control. Kutner to a lesser extent, but he shaped things with his shocking exit (and went on to the White House, of all things.)
Like almost everything else in the 8th season, the last two fellows (Park and Adams) were thinly drawn cartoons who added nothing to the show.
Without reading anything but the OP:
Angel was good from the get-go, but it improved significantly with the substitution of Wesley for Doyle and the addition of Gunn & Fred. Even Connor was a good thing.
:eek:
Like hell!
Jennifer and Mary Anne weren’t part of the first season of Perfect Strangers but they totally rounded out the show once they got there in the second season.
After that Connor comment, you have no room to criticize. 
Babylon 5
Replacing Jefferey Sinclair (Michael O’Hare) with John Sheridan(Bruce Boxleitner)
Marcus Cole (Jason Carter) Having him around opened up many side plots that no other character really would have felt right doing.
:: removes left glove, slaps silenus across face ::
I shall have my satisfaction, sir! Name the time, I shall name the weapons!
July 42, 13,672 BCE
Slightly after tiffin.
I’ll send a squad of thugbots over with a continua buggy to make sure you show up on time.
Both *Buffy *and Angel really had pretty good success records for cast additions, as several others have pointed out.
I thought Jonathan Banks added a lot to the fifth season of Community, though I suppose he never qualified as a main cast member.
Parks and Recreation improved quite a bit dropping Mark Brendanawicz and adding Ben Wyatt and Chris Traeger.
The Professor and Mary Ann. 
Agree with Reverend Jim and Sgt Dietrich.
Not even in jest.
You might as well mention Scrappy Do.
They were there, just not in the song. Right? 
And the rest…
In the “replacement characters” category:
Adding Ted Danson to the cast of CSI: has brought a good spirit and reinvigorated the cast. There was nothing really inherently WRONG with Lawrence Fishburn, he had an OK character with a “twist” that was revealed a bit too soon, but Danson has brought a unique personality, cadence, and chemistry with the cast that’s been missing for a while