When Acting-Captain Spock orders the Enterprise to be evacuated, Sulu refuses to leave Spock to die and the rest of crew also refuse to leave.
Spock apologizing to Uhura for his behavior and how he hurt her because of the volcano mission. They share a kiss once they return to the Enterprise, with Uhura even standing on her tiptoes.
His entire monologue is beautiful. It's the most tender we've seen him be towards Uhura.
Uhura kisses his helmet for good luck. Blink and you'll miss it, but Spock was actually leaning his head in towards Uhura when she kissed his helmet and it is adorable. 
Another blink and you'll miss it moment comes before that; when she was helping him into the suit, Spock begins to repeatedly tell Kirk over his comm about how he can't violate the Prime Directive. As he says it, Uhura looks up and gives him a smile, in a way that says "only you can stress that over and over when you're about to be lowered into a volcano". Spock may be an impossibly by-the-book Vulcan, but he's her impossibly by-the-book Vulcan.
As Spock prepares to beam down to catch up with Harrison, he and Uhura share a heartfelt look.
Uhura: Go get him.
Uhura spent pretty much the entire first film thinking Kirk was an arrogant sarcastic jackass, but with this one line she makes it clear that he's managed to earn her respect and affection. Perhaps she doesn't hold him quite as high in her esteem as Spock does, but goddammit, she cares enough that she'll support her boyfriend flat out murdering the man who caused his death, and will do so with no regrets at all. It is made very clear that if Khan wasn't needed alive to save Kirk, not only would she have supported him, she'd have helped, and gladly.
Khan wears a small smile while in cryo sleep with the rest of his superhuman compatriots, whom he previously thought he killed after getting tricked by Spock. The guy may have been one of the most unrelenting war criminals of all time, but at least he was reunited with his family.
Look closely at the scene when he surrenders himself, especially if you've watched the movie before. He asks how many torpedoes there are, and when Spock tells him, you can see by the expression on Harrison's face that his broken heart has been remade. Imagine thinking your family is dead; you're on an unfamiliar planet, broken and guilty inside, expecting to live out the rest of your days alone...and then someone tells you your family is still alive.
At the end of the film and the beginning of the five-year mission, Kirk warmly welcomes Carol aboard the Enterprise, to which she responds, "It's good to have a family." He then asks Spock where their next destination is, to which Spock defers back to him.
There is an undeniable smile on Spock's face for that entire scene.
During that exchange, Spock casually calls Kirk "Jim", dropping his usual formality.
The fact that one of the most meaningful moments between the central Power Trio is shared quietly between just the three of them, especially since they didn't get to shine much together in this particular film.
Also, Kirk telling Spock that despite the fact that Spock got him relieved of his command he's still going to miss him.
Even when Spock fails to verbally reciprocate, Kirk's reaction is more fondly exasperated than upset. He might have been pissed that Spock's Vulcan honesty got him in trouble, but he doesn't resent his friend for being who and what he is.
Uhura offering her condolences to Kirk over Pike's death. Even if they're not the best of friends, she knows how much Pike meant to him and she understands how it affected him.
When McCoy's arm is caught in the torpedo he and Carol were studying, she refuses to leave his side until a way is found to free him.
After he's freed, Uhura can be seen sighing with relief before walking over to Spock. It's not seen what either of them do, but it's an easy guess she needed a little comforting after that shock of almost losing a friend.
The scene in the bar with Kirk and Pike. Kirk goes there depressed because Pike demoted him and most likely feeling awful that Pike, his father figure, was so angry and disappointed. But Pike shows up and after some necessary snark and tells Kirk he's gotten him another another job, another chance, as his first officer. Kirk looks so grateful he might cry, and Pike tells him "It's gonna be OK, son." SON. Gahhh!
Strangely enough, Spock's snark during the debriefing scene with Pike. He's not snarking for the hell of it; he's annoyed that Pike is scolding Kirk! That entire scene can pretty much be described as a father scolding his younger son with the older one coming to the younger's aid, with the younger one mad at the older for telling on him.
An example that may fall under Fridge Brilliance: Harrison offering to save the girl in the beginning, in exchange for her father becoming a suicide bomber. He could have easily just said he would help her, and gone back on his promise. But as it's revealed later, he has a family too; his crew, who he cares about. He knows what it feels like to lose family, unable to protect them.
When Khan beams Scotty, Kirk and Carol Marcus into the cell, while Scotty yells at the guard you can see Kirk cup Carol's face in an "Are you okay?" gesture.
When Kirk fails to convince Admiral Marcus to spare the Enterprise, there's a shot of Spock and Uhura in the back. Everyone is convinced that they are all about to die, and they're standing side by side. It's very small; in fact it's just a shot. They're not even really touching. But the fact that they're standing together instead of at their normal stations says so much.
A few moments before that, you see Spock is the one who walks over to her. Aww...
in the official novelization by Alan Dean Foster it's said they are holding hands
A more subtle one between Kirk and Uhura. He complains about Spock to her, referring to him as her "boyfriend". After a second he looks at her, then looks down saying: "I'm sorry, that was inappropriate." Would he have done that in the first movie? Definitely not. A very clear sign that Kirk is growing up.
And when he realizes Uhura and Spock may be having relationship troubles, he looks worried, showing that he fully supports their relationship. Especially heartwarming when you remember that in the first movie, he was constantly hitting on Uhura and was shocked by the reveal that she was with Spock.
Carol's plea to her father not to kill the crew is heartwarming when you think about it. She's known these people only for a few days, yet she's willing to be murdered by her own father if that's what it will take. What's particularly heartwarming about it is that in many films, novels, shows, etc., when confronted with a similar situation, the child at least considers siding with the parent. But Carol will have none of it, because these are innocent people, her friends, and she has no interest in letting them die.
In the same more implied way or play off of expectations, the rest of the crew never even considers that she might be siding with her father or spying on them. Given the fact that they barely know her and that she lied about her identity, forged her way onto the ship, and is the daughter of the bad guy, one would expect that the others would suspect her of working against them. They never do.
For British viewers, it would be the subtle inclusion of the Union Flag flying in London. Even in the 23rd century, it seems that there will indeed always be an England.
Values Dissonance: It's simultaneously a slap in the face to Scottish viewers who'll be voting in favour of independence in 2014.
A very small one and probably not intended by the film makers but the name of the ship that Spock would have been transferred to was named the USS Bradbury. Considering the passing of sci-fi author Ray Bradbury last July, it's pretty sweet to honor his memory and contributions to the genre.