i'd say Ian Payne from 5Live in 2003 was a big deal. He was signed up as Richard Keys' number 2 and was 5Live's main weekday sports presenter. I think they decided to go down the Sky Sports News route (Ed Chamberlain, Dave Jones etc) when they wanted to make pundits such as Neville and Carragher the star - rather than the presenter - and rebuild things after it was clear Keys and Gray wielded too much power.
The arrival of Ian Payne was quite interesting, he arrived when Sky got the rights to the Champions League and he did Saturday and Monday matches so Richard Keys wouldn't be on five days running. But Payne didn't have much in the way of TV experience - up until then he'd only done the sport on News 24 - so he seemed a bit ill-at-ease at it, and never really managed to really relax in front of the camera. Then unfortunately for him, in 2005 Jeff Stelling was about to be poached by ITV - he'd got as far as handing in his notice - and to keep hold of him they offered him the job of presenting Premier League matches. That meant he took on Payne's job, and Payne was moved down to do the Cups alone (though he did do the Cup Final in 2006) before being pretty much confined to Sky Sports News. He stayed with Sky until about 2010, so he had a decent run there, but it was a bit of a shame he gave up the radio, where he was excellent, to become a bit of a spare part on TV.
As you say, by the time Keys had to, er, go away he was as prominent on Sky as he'd ever been - he was sometimes presenting five days a week, with Premier League matches on Saturday, Sunday and Monday, and the Champions League on Tuesday and Wednesday. I always remember Des Lynam saying he was never much of a fan of Keys' presentation style, saying he always felt he came across like a man who knew something that he wasn't going to tell you.