"The Magicians" and "The Magician King" are brilliant deconstructions (and subsequent reconstructions) of hero, utopian, and magic tropes, among others. The main character is an extremely genre-savvy person, but finds that none of these things are what he thought they'd be.
Before Don Quixote, there was Ariosto's Orlando Furioso, whose intense love for Angelica basically turned him into The Incredible Hulk after he finds out that she's a normal, human woman who's had a fling with a shepherd, and not a virginal Princess Classic.
This scene was homaged/parodied in Don Quixote when the titular character (who doesn't realize that Orlando is a satire) decides to recreate it. The only thing more ridiculously unheroic than a man going violently insane over a woman who doesn't want him is a man trying to go violently insane over a woman who doesn't want him.
Ender's Game is a deconstruction of the Kid Hero and Boring Invincible Hero. By the time the book ends Ender abandons Earth forever, has killed all but one of a decidedly non-hostile species that accidentally antagonized humanity before they realized we were sentient, doesn't hook up with his love interest (because, you know, he doesn't get one) and had his ass handed to him psychologically. Oh, and he accidently killed two fellow students but was never told about it, but he's smart enough to suspect it and feel guilty.
Ender's Game also deconstructs the Groin Attack. Yes, really. And yes, it really is as bad as it sounds... possibly worse.
The book also deconstructs the Bug War. You see, the buggers only killed humans because they had assumed our individuals were drones like theirs, when they realize we possess sentience on an individual level, they accept humanity's retaliatory invasion with a resigned, "oh… the humans didn't forgive us…" They actually turn out to be a fair bit nicer than humans at least as far as respecting other sentient life.
The novel Nuklear Age by Brian Clevinger subverts and deconstructs almost every aspect of The Cape and rebuilds it in his own image.
The Neverending Story provides a particularly satisfying deconstruction of the Canon Sue. Bastian gets the power to remake an entire world as he sees fit, but with each wish that gets granted he loses one of his memories and becomes more and more of a moron and a jerk. Finally it's up to the story's real hero to save his ungrateful ass, and when he finally realizes what's been going on it's a thing of beauty.
The various 'stories' also serve as deconstructions of various tropes, especially in the second half where Bastian's attempts to help don't go as intended. For instance:
Always Save the Girl and Standard Hero Reward are both deconstructed with the character of the Hero (actually his title) who is madly in love with a princess who won't give him the time of the day. Bastian uses his powers to create a situation wherein a dragon kidnaps the princess and the Hero can rescue her to make her fall in love with him. It's briefly described that the Hero endures a number of dangers and saves her, and she does fall for him... except he's no longer interested in her after going through so much for her. So there's only so far The Dulcinea Effect will take you.
Said Hero's three companions (of the same class) deconstruct Knight In Shining Armour and Undying Loyalty - after Bastian earns their respect, they swear to serve him forever... This unfortunately includes trying to do amoral things against their benevolent nature, and also when Bastian disappears they dedicate their lives to finding him, ultimately Breaking the Fellowship and going their separate ways.
Magic A Is Magic A and Applied Phlebotinum are deconstructed when Bastian - in a very special city with an acidic lake, full of inhabitants who wish to know their own origins - creates a story for them which becomes fact. That would be fine... except that said origin involves the acidic 'water' of the lake coming from a group of grotesque, ever-weeping creatures, whose acidic tears created the lake but also unearthed the one metal which it withstands (the city's main source of profit as well). Bastian's attempt to make them happy (by changing their forms into butterfly-like beings) comes back to bite him much later when they reveal to him that without their tears, the lake has dried up and there is no way to mine for the special metal anymore. He is threatened and almost killed by them to try and change them back into their sorry prior forms, before Atreyu and Falkor save him.
Conservation of Ninjutsu is deconstructed in the Warhammer 40000: Gaunt's Ghosts novel Ghostmaker, where the victory of Gaunt and a small group of troopers (exalted by some Eldar sorcery) over a thousands-strong Chaos force without taking casualties is found to simply not make sense given the tactical data, which should have had them killed to the last man, and is written off by analysts as a phantom engagement.
Dan Abnett also deconstructed The Smart Guy in his Warhammer 40000: Eisenhorn trilogy. Eisenhorn's savant, Ueber Aemos, is the walking databank he is because of a "meme-virus" he acquired that gives him a compulsion to keep gathering knowledge, culminating in memorising the entirety of the Malus Codicum and summoning a daemon in an attempt to protect Eisenhorn.
It also had some fairly lengthy deconstructions of Always Chaotic Evil, basically arguing that any species you could call "sentient" must have the potential to choose good or evil.
The Mistborn books deconstruct the Evil Overlord in the character of the Lord Ruler- he's introduced in the first book and pretty much played straight as an inhuman/superhuman force of evil though we do get a bit of his backstory; subsequent books delve deeply into his personality, history, and motivations, ultimately making him out as Not So Different from the heroes.
It also Deconstructs many, many tropes of rebelling against an Evil Overlord like him. For example, killing him doesn't bring easy succession-it drives the land into chaos! And now the heroes, who killed him off, are in government, and it shows the hardships of that.
Stardust makes the Deconstruction of the Engagement Challenge a plot point, by showing and openly talking about how stupid an idea it is, and how if someone makes a joke about an impossible task to evade your flirtations, this doesn't mean that they actually want you to do it. Victoria spends the entire duration of the Hero's quest torn between being guilt-ridden and terrified that she's probably sent an old childhood playmate to his death, and terrified that he'll come back, because she's in love with someone else. The book also covers the unpleasant end of a Mayfly-December Romance, although the movie version offers a way out.
Paradise Lost is a deconstruction of Draco in Leather Pants in its portrayal of Satan. He starts out all Bad Ass and charismatic, but as we get to know him more and more, he see that he's a whiny, self-pitying bully who bows to peer pressure from the other demons, bangs his own daughter and arguably isn't even all that badass when compared to, say, Michael or Kung-Fu Jesus. The intention was to make the reader acknowledge that they felt the allure of sin but also that it leads nowhere good. However, he is for the most part still portrayed sympathetically enough, to the point that actually seeing him as living up to those traits isn't that far off, if he wasn't emerged in a sea of Wangst.
Atlas Shrugged also deconstructs I Just Want To Be Loved with James Taggart's relationship with Cheryl. Instead of being loved for owning a company, for being skilled or for even being a nice person, he wants to be loved for what he is, and that's pretty much nothing.
Atlas Shrugged is the story of an everyman refusing to submit to an evil corporation. The Fountainhead is the story of a corporate head refusing to submit to the people. Which is supposed to be the correct version, we may never know.
Warrior Prince: Does this with Prince Attrebus. Instead of going out and winning glorious battles for The Empire, he is tricked into believing he has done so, and subsequently gets all his men killed, realizes that just being a prince doesn't make a person a great fighter, and is forced to face his own failings before he can try to be a real hero.
Action Hero: Annaig. She reads a lot of adventure books, and has an extreme desire to be an adventurer herself. When she finally does get to go on a "real" adventure, most people she cares about are killed, she is constantly forced to keep her morals in check or else she is worried she will become just as bad as the people she's fighting, she realizes that destroying Umbriel will likely kill hundreds of decent people along with the not-so-decent ones, and spends most of her time just trying desperately not to die.
The Harry Potter series deconstructs the Chosen One trope. Harry's status as the chosen one wasn't decided by fate, but happened because Voldemortthought it was fate and leaped into action with an impulsive decision. Moreover, while he's competent with magic (better at some things than his peers), he's not a genius or exceptionally gifted in magic like his adversary (who is described as one of the most powerful wizards in wizarding history). His heroic actions save lives but, until the end, do not bring him glory - on the contrary, they end up being used to label him as "reckless" and "unstable" for a long time. He ultimately triumphs over Voldemort not because of his superior talent, but because Voldemort makes a major mistake and is arguably brought down by his own blindness and arrogance.
Another deconstruction takes place in regards to Comforting the Widow. A certain Death Eater named Severus Snape can't get over being Lily Evans-Potter's Unlucky Childhood Friend, who is more or less Happily Married to James Potter and is the mother of baby Harry. He panics when his boss, Lord Voldemort, decides to kill her alongside Harry for being his mom and a "mudblood", and then asks Voldemort to only kill her husband and child so he can comfort the widowed Lily and ultimately have her as his trophy wife of sorts. Voldemort's answer is "NO DAMMIT" and he coldly kills Lily too, when she goes Mama Bear to protect baby Harry (and her Heroic Sacrifice protects him from beyond the grave too). Snape is so crushed after losing the only person who once cared for him due to his own actions, that he has a Heel Face Turn and becomes a Good Is Not NiceAtoner. Not to mention, Dumbledoreharshly calls him out.
Actually, Voldemort agreed to spare Lily, but found at the last moment that he would have to go through her to get to the baby. He told her to step aside, if she did he would have let her live; but she couldn't step aside, thus making it a willing sacrifice.
A deconstruction of a lighter shade comes with Luna Lovegood's Cloud Cuckoolander tendencies, which have left her an easy target of teasing and ridicule amongst the other students. (In example, she tells Harry that the Ravenclaw kids prank her by hiding her stuff and forcing her to search for it all alone). Consequently, Ginny Weasley had been pretty much her Only Friend at Hogwarts until her 4th year at the school... However, neither of these facts bothered her significantly, and she does what she can to live her life at the fullest.
Also deconstructs The Power of Friendship; there isn't any magical reason Harry's friends are an advantage (indeed, Ron, like Harry, isn't really someone special) but Harry's willingness to make friends means that he has people by his side fighting for his cause because they believe in him, whereas Voldemort tries to command loyalty through fear and power. People think nothing of betraying him (one doing this in particular very important in the process of his undoing) or at the very least not giving him their all if they've come to find that it's no longer to their advantage.
Cho Chang serves as a deconstruction of the Relationship Sue trope. She is introduced as a pretty and popular girl who is an excellent Quidditch player. But when she and Harry finally get together a combination of her still grieving for Cedric, Harry knowing nothing about girls and a few misunderstandings show that they are not very compatible and they remain friends. In another variation Ginny Weasley may reconstruct the trope by realising her crush on Harry won't amount to anything and working on becoming a stronger and more capable friend to him... which is the very reason he falls in love with her.
Speaking of deconstructing The Chosen One, The Wheel of Time does a deconstruction in the form of Rand Al'Thor who is nearly driven insane by the pressure of having the entire world resting on his shoulders and begins to use much darker methods to make sure everything stays together. Eventually he realizes what he's doing wrong and gets better.
The Chronicles of Thomas Covenant is yet another deconstruction of The Chosen One. After seemigly getting knocked out after getting hit by a car, he wakes up in a magical land, and spends the rest of the series refusing to accept any of it is real because he thinks it's all in his head and he's going insane. And to top it off he's a Jerk Ass, highly cynical loner who really is only a hero because the villain is someone that gives most others nightmares.
The first series also uses Lena to deconstruct Loving Force.
The Honor Harrington series deconstructs The Federation, in the form of the People's Republic of Haven (or, arguably, the Solarians). Much more on the trope page.
In Dostoevsky's classic The Idiot, he ruthlessly deconstructs the Purity Sue. Myshkin is basically Jesus reincarnated, being possibly the most pure representation of what the Church expects that people should try to be like. The problem? Everyone who doesn't want to be like this (that is to say, everyone except Myshkin himself) takes advantage of his personality for all it's worth because Humans Are Bastards.
The novel Speeding Bullet by Neal Shusterman takes a knife to the idea of Jumped at the Call. Nick saves a girl from a subway train, then a man from a burning building, then gains the attention of a rich, hot girl, and keeps running across situations for him to intervene in. Except his girlfriend has been paying people to set up situations to feed his Adrenaline Junkie habits. And when he really needs it, he can't find his courage anymore.
From the same author, "The Shadow Club" involves a group of teenagers getting back at others by playing pranks on them. Naturally, someone takes the "harmless" pranks too far; because that's what happens when you give people power over their foes.
Wuthering Heights deconstructs All Girls Want Bad Boys, by showing exactly what happens when girls fall in love with troubled, angry men. Heathcliff is a 'bad boy', and Bronte shows exactly what this means; he's unstable, vindictive, violent, selfish and vicious. The relationship between Heathcliff and Catherine is depicted as being intensely passionate, but also intensely unhealthy (not least because they may or may not actually be brother and sister), and Heathcliff's response to being spurned for another man is to embark on a single-minded crusade of vengeance that ultimately results in the ruination of both lovers and their immediate families for absolutely no point whatsoever. As if this wasn't enough to illustrate the point, Edgar Linton's foolish sister Isabella elopes with Heathcliff because she's attracted to his bad-boy image. She gets what she wants, but not in the way she expects; an abusive husband who is openly contemptuous and violent towards her, and makes no secret of the fact that he only married her to get at her brother. This hasn't stopped a Misaimed Fandom growing around Heathcliff, however, who even to this day is considered a model of a romantic hero despite the fact that he's pretty much a sociopath — something that Bronte intended to make absolutely clear.
It also shows that what happens when good boys fall in love with troubled, angry women who are in love with said troubled, angry men...
Romance, as a genre, is one of the easiest to deconstruct, simply because by its very nature it is fantasy-driven. There are eerie parallels between the 'romance' and 'porn story' genres (aside from the fact that a story can be both at once), in that both exist to embody fantasy satisfaction of impulses that in real life must be restrained by the necessities of duty, common sense, and sanity. Drama is good as entertainment but rapidly becomes exhausting and draining when you have to live it.
Even optimistic adventure stories, while free from overall deconstruction, aren't necessarily free from having individual tropes deconstructed. Case in point, The Mysterious Island by Jules Verne, which blatantly falls on the Ideal side of the scale. Thus, the trope of Robinsonade is played straight by the main protagonists, but is deconstructed by Sixth Ranger Ayrton who goes mad from being isolated for so many years and probably would have died an agonizing death were it not for Nemo telling the castaways about his island.
When the Windman Comes by Antonia Michaelis deconstructs Mr. Imagination. The girl Paredoile and her mother live in a world filled with their imagination, and some of things they imagine are very wonderful and exciting - but most are evil and threatening - like the titular Windman. They live in constant fear of imaginary phantoms, which leads to both of them having no friends (which is especially hard for the girl), brings further hardships, and even creates some very real dangers (like when Paredoile's mother refuses to let her be treated in a hospital for fear of Windman). Ultimately, it takes an intervention of the hero, a Down-To-Earth kid, to break them free of that.
The Godfather, one of the most famous Mafia sagas in fiction, made a big deal out of the Nothing Personal trope. But in the novel that inspired the films, Michael Corleone himself deconstructs the trope in this speech to Tom:
Michael: Tom, don't let anybody kid you. It's all personal, every bit of business. Every piece of shit every man has to eat every day of his life is personal. They call it business. OK. But it's personal as hell. You know where I learned that from? The Don. My old man. The Godfather. If a bolt of lightning hit a friend of his the old man would take it personal. He took my going into the Marines personal. That's what makes him great. The Great Don. He takes everything personal. Like God. He knows every feather that falls from the tail of a sparrow or however the hell it goes. Right? And you know something? Accidents don't happen to people who take accidents as a personal insult.
The title character of Alexander Pushkin's Eugene Onegin is a deconstruction of a Byronic Hero.
Brilliant, but Lazy: Benjamin is the smartest animal in the farm but refuses to become a leader not so much because he's lazy but out of fear. He still wouldn't say anything even after Boxer got sold to the knackers.
Humans Are Bastards: The animals refusal to adopt human ways allows the pigs to screw them over.
Seven Sorcerers by Caro King deconstructs Plot Armor. The heroine Nin Redstone, a young girl, has it, and therefore survives many dangerous situations unscathed - physically that is. However, the Plot Armor, as usual, does nothing to prevent her from getting into such situations. In fact often she get into bad situations precisely because somebody wanted to exploit her luck, in fact, this is the whole reason she got dragged into the whole mess in the first place, and Nin has to deal herself with the psychological scars of her dangers. Also she developes huge Survivors Guilt, when other people die around her - partially because her Plot Armor doesn't seem to care about collateral damage.
Pride and Prejudice deconstructs Gold Digger. The Bennet sisters are greatly pressured by their mother to find a wealthy husband so that they can live comfortably after their father dies. The oldest daughter Jane genuinely falls in love with a rich man Mr Bingley but due to her snobbish mother's efforts and the fact that Jane is a Love You and Everybody kind of person, Mr Bingley's friend Mr Darcy mistakenly believes that Jane is a Gold Digger and doesn't actually love Mr Bingley.
The second oldest daughter Elizabeth recognizes how destructive the Gold Digger mindset is. But she eventually comes to a compromise. She won't marry a poor man but she would only marry a rich man if she falls in love with him. Her intentions are genuine when she actually shies away from the rich but snobbish Mr Darcy. It does take a polite trip to his beautiful estate and hearing how his servants heap praises about him to make Elizabeth to consider letting him court her.
The Redwall book The Outcast of Redwall does this to Always Chaotic Evil. Veil Sixclaw is a ferret, classified as "vermin" in the setting. He's taken off a battlefield and raised by Redwallers. However, anything that goes wrong during his stay is immediately blamed on him, and he eventually decides to be what they expect. Only his foster mother believes in him. In short, the Redwallers, sans Bryony, never gave him a chance to NOT be evil.
The Emerald City series deconstructs, among other things, Black and White Morality. Said morality is, from book 4 on, enforced by the ability of Big Bad to magically force any morally grey charachter into his service. The result is that, since most of those are actually s, one often feels more for them than for actual heroes (especially since heroes can get Back from the Dead in most cases).
Book ten deconstructs Become a Real Boy. Tom, a living teddy bear, magically becomes a human and a great warrior... and dies per Heroic Sacrifice in the very first battle, whereas killing him as teddy bear would be all but impossible.