Robb Stark was very stoic initially; Talisa defrosts him.
Brienne to Podrick, as she didn't want a squire, so she often berates him. She does eventually come to respect his loyalty and apologises for being harsh towards him, however.
Despite their rough introduction, Lyanna Mormont eventually mellows to Jon and Sansa. She even nominates Jon as the new King in the North, which the other lords accept.
Margaret "Hot Lips" Houlihan on M*A*S*H. During the series' early "comedy" years, she started as a bossy, unlikeable head nurse. She had many defrosting moments (mostly with the laid-back Hawkeye) after the first season, but her first defrosting episode was "The Nurses", and since, due to trouble with men like Frank Burns and Donald Penobscot, although she's still a hard-nose (she is an Army major, after all), she comes off as a significantly more developed character with a warm heart who will volunteer rather than send others into danger.
Glee: Kurt, especially after his transfer to Dalton means he no longer needs to be constantly on the defensive just to survive high school. And he is indeed a queen...
Romana. A number of fans posit that the Doctor and she had a relationship (no doubt aided by the brief marriage of Tom Baker and Lalla Ward).
Amy Pond is an example, considering the Doctor ran off without her twice and she was pretty bitter about it.
Amy: I grew up. The Doctor: Don't worry. I'll soon fix that.
Ice King variant: The Twelfth Doctor explicitly tries to distance himself from his companion Clara by being less affectionate and open than his predecessor (who ultimately thought of himself as Clara's boyfriend). Over time, however, he defrosts at least as far as Clara is concerned to the point where he becomes more openly affectionate with her, less abrasive in discourse with her — and undergoes an epic and universe-threatening grief-driven Heroic BSoD when she is killed. Although recovering from this requires him to lose the deep feeling he had for her via Mind Rape and he's frosted up a bit at the top of the Christmas Episode that follows this story arc, his actions upon his path being crossed with River Song's prove he'll never truly be the Ice King again.
Cordelia Chase from Buffy and Angel starts out as the definition of this trope (especially towards Xander and Doyle on the respective shows) and by the end of the series has evolved into a warm caring woman.
Star Trek: The Original Series: Spock's relationship with Kirk is a platonic example of this. Although it takes years for Spock to fully accept that emotions are a good thing, most of his moments in between are due to the captain.
Kirk also defrosts a haughty monarch in "Elaan of Troyius."
Star Trek: Deep Space Nine: Odo tried very hard to remain the dispassionate observer of humanoid behaviour but he found himself making friends despite himself.... friends that were determined to make him enjoy having friends. Friends that won this battle in the long run.
In an interesting case of a role defrosting an actor, the title role on Murphy Brown did a lot to soften up Candice Bergen's image after years of being known as a cool debutante. Her dry wit has been a staple of most of her roles since.
Sherlock in BBC's Sherlock over the first two seasons. Although not without bumps along the way, his friendship with John helps Sherlock slowly learn to open up to the other people in his life (albeit in an eccentric, clumsy way) to the point where his priorities at the end of the second season are wildly different from those in the pilot, or even the end of the first season.
Now that we have Mary, Sherlock, and John, despite the fact Sherlock claims himself to be a sociopath, (we know he isn't, since his goals in Series 3 were a lot different) and shooting Charles in front of everyone, including Mycroft, it shows that he's a lot more caring than he was before.
Sarah Jane Smith of The Sarah Jane Adventures started out "positively frosty!" - and can you blame the woman, considering aliens are out to kill her? - but softened considerably after meeting Maria and adopting Luke. Later she goes on to say that Luke gave her something to live for.
Ashley Jeurgens from The Secret Life of the American Teenager. Started out being the down-to-earth girl who said won't repeat Amy's mistakes, being the voice of reason and trying her best to be a good daughter to her almost crumbling family. Now, she might be steps away from being almost like Amy...
In Dance Academy, Abigail is initially quite a horrible person, but Sammy's persistence and support of her eventually makes her much nicer and she eventually falls in love with him despite her claims that she "[doesn't] do emotions." Christian starts off very cold and distant from everyone and isn't too keen to make friends. Tara, Kat and, again, Sammy all play a role in making him a warmer person.
Marguerite in Sir Arthur Conan Doyle's The Lost World. In the beginning she appears cold and uncaring. She is perfectly willing to sell Veronica for a way home of the Plateau and usually seems to not care about any of the others. And then one looks closer. She grows to care about the others a lot. When Summerlee gets stung by a gigantic bee and hallucinates about his dead wife she resumes that role to comfort him, she looks out for Malone and Veronica, helps Challenger and becomes Roxton's confidante whenever the memory of his brother breaks him. But although she learns to trust every expedition member with her life she's still careful about letting them know about her past and why she really came to the Plateau.
Dana Scully of The X-Files is this way. She is naturally steely and emotionally distant to everyone, but especially to Mulder in the early seasons. Eventually, he breaks through and she develops a Sugar-and-Ice Personality, in which she remains cool and distant to everyone else, and a little bit freer with her feelings with Mulder.
Althought the defrosting is only partial, Alex in Wizards of Waverly Place could be considered a example, either throught Jalex,Dalex or Malex.
Lady Mary Crawley of Downton Abbey slowly but surely defrosts over the course of the first two seasons thanks to the influence of Matthew. She evolves from someone utterly selfish whose only concern upon her unofficial fiance's death is how long she has to wear black, to a woman who realizes her own mistakes and eventually admits them to those she loves. She even outright states that Matthew sees her as a much softer person than others do. After Matthew's untimely death, Mary reverts temporarily to her icy ways.
Lexa from The 100 tries to be stoic and ruthless, with no attachment to people as individuals, but only to her duty as the Grounders' Commander. However, as she works alongside Clarke, Lexa begins to develop feelings for her, enough to make her reconsider her belief that Love Is a Weakness, and to trust Clarke even when her pragmatic logic says she shouldn't. Subverted at first when, despite her feelings for Clarke, Lexa still abandons her in the middle of a crucial battle, seeing an easy victory for her side as more important than her personal attachment to an ally. Later on after reuniting with Clarke, Lexa makes it clear she greatly regrets abandoning her and then slowly but surely warms up to Clarke, even offering to implement more merciful and forgiving policies as Commander of the Grounders. Unfortunately, Lexa ends up being shot and dies in the very same episode where she fully melts.
Wife Swap gave us the mom of a fun-free house who had to deal with a loony magician. When she realized she was fighting an uphill battle, she took off and made her way to the customary meeting between the couples in tears.
On The Astronaut Wives Club, Louise Shepard gradually defrosts, partly thanks to the friendship of her fellow wives and Max.
In The Walking Dead, Michonne started out this way. She lived with Andrea for months, yet never revealed anything about her past. When Rick kept her hostage, she could do nothing but scowl stubbornly at him, even retaining her mute state after becoming an official member of the group. Carl eventually coaxes her out of her shell, and it's Rick's refusal to hand her over to the Governor that cements her Undying Loyalty to him.
Enid is introduced as The Quiet One, who shuts people out due to her Dark and Troubled Past. After growing close to Carl, and witnessing Glenn and Maggie's devotion to helping her cope with the Crapsack World, she warms up to them and becomes a more involved and vocal member of the team.
The Handmaid's Tale: Serena Joy begins to treat Offred much more nicely when she finds out Offred's period is late, even going so far as starting work on a much nicer bedroom for Offred. Before the reveal, she seemingly opens up to Offred about how happy having a child will be and how much she and the Commander had tried for a baby in the past. Naturally, once she finds out Offred had her period... it's right back to business-as-usual. However she then develops as a character in season two.
Legend of the Seeker: Cara. She slowly warms up to Leo, who actually gets her to smile for the first time. It's only after he dies that Cara admits she had feelings for him though. It also helps that she learns that her father never betrayed her and refused to say he did, forcing the Mord-Sith to burn his vocal cords with acid to keep him from denying their claims.
In For the People, Kate starts the series very closed off, but starts to at the very least tolerate those around her as time goes on.