When Ned is searching for a lead on Jon Arryn's killer, Varys tells him: "There was one boy. All he was, he owed Jon Arryn, but when the widow fled to the Eyrie with her household, he stayed in King's Landing and prospered. It always gladdens my heart to see the young rise in this world." Ned assumes Varys to be talking about Ser Hugh, Jon's squire. Varys is actually making a cryptic reference to Littlefinger.
Hizdahr hates being called "your grace", because in Meereen the Graces are priestesses and prostitutes. In Hizdahr's eyes, every time Ser Barristan calls him "your grace", it's insulting his masculinity at best or implying he's a prostitute at worst.
Sansa is frequently described as a "little bird," because she's kept in a gilded cage, always says sweet things and repeats back whatever is expected of her. She's taken under the wing of Petyr Baelish, masquerading as his natural daughter. Baelish changed his sigil to a mockingbird, which also repeats noises made by others.
There's some definitely Stealth Pun humor with the Kettleblack brothers. Their accusing others of their own crimes fits with the proverb about what the pot called the kettle.
There's likely a heraldry Stealth Pun in Stannis' coat of arms that has a the Baratheon stag enclosed in a flaming heart. A hart is another word for a stag.
The sigil of house Baratheon is a stag—the term "horns", refering to being cuckolded, is derived from the stag's custom of giving up its mate after losing a fight. House Baratheon is plagued by all kinds of adultery. Robert is constantly cheating on Cersei and is in turn cuckolded by her, Stannis makes shadow babies with Melisandre, and Margaery Tyrell is only "officially" a virgin on marrying Renly.
In A Storm of Swords, Tyrion thinks: "There was this to say about weddings over battles: it was less likely that someone would try to cut off your nose." As two particular weddings in that book proved, weddings are worse than battles sometimes.
In A Game of Thrones, Arya jokes about her hypothetical coat-of-arms, wondering if it would be a wolf with a fish in its mouth. Later on Arya, warged into Nymeria, pulls Catelyn's corpse out of the river.
Theon is described joking about Hodor that whatever else you could say about his intelligence, he definitely knows his own name, though he apparently forgot that "Hodor" isn't Hodor's name. Theon then becomes so tortured that he's been conditioned to forget his own name.
Maps of the world◊ show that many coastlings and the land across from them fit together, such as the Sea of Dorne and that headland in the Disputed Lands, or Shipbreaker Bay and that headland north of the Sea of Myrth, or the Sea of Myrth itself and the headland Rain House is on. This is in accordance with real-world plate tectonics, such as how South American and Africa fit together.
Combined with Fridge Horror. In a lot of aspects, Theon is shown to be a foil to Jon Snow. Because of this, its interesting to note that while Jon performing oral sex on Ygritte is one of the most romantic scenes in the story, Ramsay forcing Theon to perform oral sex on Jeyne Poole is one of the most horrific.
Jalabhar Xho is an analogue to Viserys, another exiled "beggar king." Just like Viserys, he is powerless to do anything but beg those more powerful to return him to his throne. Jalabhar, however, is apparently more content to wait.
Ned is surprised to see a direwolf south of the Wall. With the Others rising, it's an early indication that the land north of the Wall is becoming uninhabitable. Mance Rayder and the wildlings eventually reveal a similar intention to flee south.
Dorne was the one Kingdom to resist the Targaryen invasion enough to manage to bargain with them and capitulated only with marriage and cultural concessions. You could easily put this down to the number of mountains and sheer expanse of baking hot sand alone. Until you remember that the people using these environments to resist being taken over had been settled by refugees from Essos — fleeing extermination by Valyrian lords. They had had plenty of time to work out what to do against dragons (and, most importantly, what not to do) what with the tales of the rout.
The bloody flux is also called "the pale mare". In the story of the Horsemen of the Apocalypse, Death rides a pale horse. Daenerys, the woman responsible for the conditions that brought about the disease, rides a literal pale male, her silver.
Dany "pointedly" asks Missandei whether Unsullied could be used against her if she decides to resell them. Later it becomes clear that Dany had no intention of selling slaves. She was trying to discover if the Unsullied could be turned against Astapor's Good Masters.
One of those most minor cases but still pretty funny is Sam Tarly unwittingly smashing Melisandre's justifications to pieces. During A Clash of Kings, Melisandre tries to justify her morality to Davos by claiming "when half an onion is black with rot, it is a bad onion." Much later, when the Night's Watch survivors have dragged themselves back to Craster's Keep and are being fed, one of Craster's wives gives out some onions, and Sam receives one that is half black with rot. He simply cuts it in half, tosses the rotten portion away, and eats the good half.
At the Red Wedding, the musicians are described as terrible, then revealed shortly thereafter to be crossbowmen, explaining why their musical talents are lacking.
A lion is also known as "King of the Jungle" and a stag as "King of the Forest". The Lannisters undermined the Baratheons for quite some time, which escalated into a clash of kings.
The Baratheons are known for their stubbornness, which is reflected in their sigil the stag. Two Baratheon bastards, Gendry and Mya Stone, are likened to a bull and a mule respectively, which are animals known for their stubbornness, thus hinting at their parentage without being actual stags.
The Ironborn worship the Drowned God, whose eternal enemy is the Storm God. The Iron Islands first fought against the Stormlands for dominion over the Riverlands and the Greyjoys later get crushed by Robert/Stannis Baratheon, who are Stormlords. Currently Aeron, a zealot, is increasingly preaching about the struggle between the two gods and it turns out that a Baratheon is coming for the Ironborn yet again and pushing them back. Both Victarion and Stannis are the younger brothers in charge of two of the biggest fleets in Westeros, are in the shadow of their older brothers, known for their lack of sense of humor, were in direct conflict with each other and ultimately ended up turning to the Red God.
The Stark family Valyrian steel sword Ice is melted down into two new swords, Oathkeeper and Widow's Wail. While the people who named these swords didn't realize it, the names allude to the Stark parents. Ned was haunted by a promise he swore to his sister on her deathbed and Cat was widowed at the end of the first book.
It seems odd that certain Houses have endured for thousands of years and yet there aren't as many members of that House as would be thought. However, looking at Northern Houses explains this. Like with Brandon the Daughterless' grandson, who was a bastard but became the Stark in Winterfell, and Beren Tallhart, who could have taken the Hornwood name from his mother's side, it shows people may have taken the names of the ancient rulers to keep prestige. Meanwhile other branches took the names of the families they married.
The idea of a long summer means a long winter and the emphasis on Ice and Fire. The long winter means there is about to be an excess of ice across Westeros. However, before that there was an excess of fire due to the Mad King, who burnt people and wanted to burn King's Landing.
Lions are predators and stags are prey. While Robert is hunting, his death is brought about by the lions.
Lord Frey is Lord of the Crossing. However he has double castles, making him the Lord of the Double Crossing, which he is adept at doing. He's also adept at making people uncomfortable for his own amusement - in other words, Lord Frey is a BridgeTroll.
The Baratheons are called Storm Lords. Robert Baratheon's weapon of choice is a hammer. Combined, it's a reference to Thor.
Barristan tells Daenerys to show mercy often; this is because he would be dead if it weren't for Robert's mercy after his rebellion.
The murder of Tywin at the hands of his son Tyrion is in several ways poetic justice.
Firstly, Tywin was found on the privy with his breeches down and took a shit as he died. When Tyrion was young Tywin had forced him to work in Casterly Rock's cisterns and drains to humiliate him.
Secondly, a dead whore was left in his bed. Tywin had previously expressed disgust over Tyrion's whoring and threatened to hang the next whore he found in his son's bed. It's also worth noting that Tywin publicly humiliated his father's mistress in part because she wore his dead mother's jewelry and Shae wore his own jewelry, the Hand of the King necklace.
Thirdly, Tywin accused Tyrion of killing his mother, though Tyrion's birth was obviously not his fault. When Tyrion does become guilty of murdering his parent, Tywin is the victim.
Fourth, Tyrion killed Tywin over what he did to Tysha. His great victories and atrocities, his family name and lineage, his power and reputation — all the things that mattered most to him in life — had no significance at all in regards to his death, only a young peasant girl whose name he didn't even remember.
The title "A Feast for Crows". It seems to refer to the fact the war is over and crows are now feasting on Westeros, a major part of the book being the fallout of the war. However, it could also refer to Euron Greyjoy, "the Crow's Eye". In this book he finally appears, becomes King of the Iron Islands, and begins his campaign to conquer Westeros, one of the chapters he appears in even has him at a feast. A feast for crows indeed.
Dany's surreal vision of a wolf-headed king reigning over a feast of dead men. It's not even as metaphorical as it first seems.
Patchface's song: "Fool’s blood, king’s blood, blood on the maiden’s thigh, but chains for the guests and chains for the bridegroom, aye aye aye."
Theon's nightmare after conquering Winterfell. In his dream Theon is sitting by a table that is surrounded by people who are dead. Theon wakes up when Robb Stark and Greywind enter the room covered with savage wounds. Theon sitting by the table foreshadows Theon's fate. In book five, Theon often reminds himself that Theon Greyjoy died in Winterfell and that only "Reek" remains.
And the Ghost of High Heart: “I dreamt a wolf howling in the rain, but no one heard his grief. I dreamt such a clangor I thought my head might burst, drums and horns and pipes and screams, but the saddest sound was the little bells."
Sandor promises to take Arya to her uncle's "bloody wedding," which turns out to be prophetic.
Petyr claims that he's slept with Catelyn, but we later learn that it was actually Lysa who slept with Petyr after a feast while he was passed-out drunk, and he thought at the time that she was Catelyn. (He later knowingly sleeps with Lysa after the duel, when he's not in the best state of mind either.) The fact that he's been making this claim for years afterwards shows how psychologically damaged he is over Catelyn.
Shae recognizes a disguised Varys because she says a whore has to learn to see the man, not his appearance, or she ends up dead. This is ironic given that she vastly misreads Tyrion when he confronts her after her betrayal, causing her death.
Oberyn says that he'd sooner die with a breast in his hand than a weapon. He dies in battle soon afterwards.
In A Clash of Kings, Bran, Rickon, and their Frey wards are playing a game in Winterfell called "The Lord of the Crossing", which they learned at the Twins. One player is the Lord of the Crossing, who stands in the middle of a bridge with a staff. The player who wants to cross must swear oaths to the crossing, which they must keep unless they say 'mayhaps' without the Lord noticing. In A Storm of Swords, Walder Frey, the real Lord of the Crossing, swears oaths to the Starks immediately prior to the Red Wedding, but sneaks the word 'mayhaps' into his phrasing. He even reminds them that he's given them leave to make the crossing at the Twins on many occasions, "and you never said 'mayhaps'" — which, according to the rules of the game, is an immediate disqualification for anyone who manages to disarm the Lord and cross the bridge.
Ned mentions Barra, one of Robert's bastards, in front of Robert and Cersei. In the next book, we learn Cersei has had her killed. She might not have even known about Barra if Ned hadn't mentioned it.
It is heavily implied that Theon has been gelded by Ramsay. Then there is the line: "Lord Ramsay never took anything but skin unless you begged for it."
On the suggestion of 'Reek' Theon has a pair of miller's children killed so he can pass the bodies off as belonging to Rickon and Bran. Theon reflects that he slept with the miller's wife a few times. Given that one of the boys is young enough to pass for Rickon, Theon may well be guilty of Offing the Offspring on top of everything else.
Littlefinger tells Ned that Starks melt when they come below the Neck. This makes sense with the whole "Starks as ice" thing they've got going, but also remember that Ned's father was burned alive when he went to King's Landing.
Also the Stark Greatsword, Ice, is melted in the South.
There are numerous references to weirwood groves being cut down and burned when people change faith. It doesn't look like a big deal (just some religious warfare), right? Then we learn, when Bran is being trained by the One-Eyed Crow, that weirwood groves contain the minds of all the greenseers, and record all the history they've ever witnessed. In other words, burning a weirwood grove is like burning a thousand-year-old library composed of sentient beings.
Almost every major castle in Westeros still has a godswood, most of which have at least one weirwood tree. Also, both public and secret messages are usually sent by messenger ravens. Now take note of the fact that this Three-Eyed Crow a.k.a. Brynden "Bloodraven" Rivers was one of the most successful and ruthless Masters of Whispers that the Iron Throne has ever had, and that his partial descent from the First Men most likely means he has access to both warging and greenseeing.
The parallel between the Baratheon brothers' health after they become king. Both Robert's and Stannis's health declined drastically once they donned a crown and people are remarking that they have become shadows of their former selves. Both went down a slow self-destructive path with a lot of self-loathing, which is especially hard to swallow for them since, like most members of their house, they were born with great physical prowess and as gifted warriors. Ironically, Renly, who was in his physical peak, was enjoying life in general and didn't care as much for fighting, got a quick death once he became king in his own right.
The Mad King put enough Wildfire beneath King's Landing to burn the city and not all of it has been discovered. If a fire breaks out in the wrong place one day...
Or one or more of the caches could be discovered by the Flea Bottom's disreputable types and hit the black market. This way, someone like Walder Frey or Roose Bolton may be revealed to possess wildfire from one of Aerys' caches, and use it against the good guys with disastrous effect.
He was a respected warrior, but was corrupted by a supernatural woman, who drained life from him when they made love and converted him to another religion. He and his brother were both kings (though few other than himself supported his claim to be a king), and were enemies of each other. His Moral Event Horizon was committing human sacrifice to appease his new god(s). He was ultimately defeated by an army from Winterfell. Now am I talking about Stannis Baratheon or the Night's King?