"Seek counsel of him who makes you weep, and not of him who makes you laugh."
— Arabic Proverb
You've got to pick yourself an advisor, but, you have a problem. Everyone around you is a Yes Man: spineless, coddling, and/or too concerned with gaining your favor or attaining their own aims to give the truth. Luckily, there's at least one person who isn't afraid to tell it like it is.
This kind of advisor isn't cruel, just blunt and outspoken. They'll never let their charge take the easy way out, never sugar coat the truth, and never be afraid to criticize. As a result, their wisdom is either completely appreciated by their students, or violently rejected if said student is the egotistical type.
If he isn't a mentor, but a regular part of the group instead, then he's usually the Deadpan Snarker, the constant criticizer, and more or less the one that annoys everyone but still gets their complete respect. All in all, this is who you want when it comes to finding a most trusted ally, and it's probably better to find people like this than your average minion.
The Good Chancellor is this as a matter of course. Often the role of The Jester in a royal court, getting away with mouthing off to the king either by couching criticism in satire, or by being (or appearing to be) mentally incompetent and thus not a threat. Another term frequently used in the past was "Naysmith" (which survives in the modern surname Naismith), meaning the one person in a royal court who could openly say "no" to the king's plans without fear of censure, forcing the king to accept criticism—the opposite of a Yes Man.
See also Hire The Critic and The Consigliere.
Genkai in Yu Yu Hakusho is one, whose favorite pastime is to call her student a dumbass/moron/dimwit/etc. and outline just how stupidly he's dealing with the current situation. All in all, she isn't afraid to trick, insult, or nearly kill Yusuke if it means he'll finally stop fooling around and see things clearly.
Also Kurama, who is both kindhearted and brutally honest, due both to hundreds of years of experience being a bandit and to experiencing the redeeming Power of Love firsthand.
Code Geass: CC is this to Lelouch because she calls him on his bull shit and points out things he doesn't want to recognize, but she's not a perfect example. While she is generally honest, she also has a habit of withholding important information as well. Like the reason she gave him Geass in the first place, or the fact that she knows what happened to his mother (as well as knowing her personally).
This is a central trope in The Melancholy of Haruhi Suzumiya. The eponymous character is initially a self-centered jackass who finds it difficult to understand that other people have feelings, and may even disagree with her. Unfortunately, she's also an extremely powerful reality warper who may have created the universe, and because of this, very few people are willing to tell her when she's wrong. That is where Kyon, the series' POV character, comes in. He is deeply pessimistic and rarely a moment goes by when he does not insult Haruhi...but he's also the only person willing to tell her the truth, and it's his unwavering honesty that kickstarts her character development into a better person. Haruhi, for her part, usually pretends to ignore him, but the first season's finale makes it pretty clear that she values him more than any other person, and he's the deputy of the group she forms in all but title.
Daine Jir, an Imperial officer from the first Star Wars. He only appears in one scene, but he criticizes Darth Vader to his face and Vader listens. Also he always listens to his stormtroopers and fighter pilots because they're the people on the front lines. He just doesn't get along with anyone else.
Tiberius' advisor Nerva in Caligula is put-upon and frequently disregarded, but valued for being the only man Tiberius trusts and respects. When it looks like Caligula will inherit, he decides he's had enough and takes a suicide bath.
Discussed in the Dystopia novel The Unincorporated Man. When the main character becomes the leader of a group of rebels, he has a Black Shirt as his advisor, because he thinks the group is out of touch with what normal people think. (Mind you, he's smart enough to choose someone who considers him a friend and won't betray him.)
King Robert calls Ned Stark to the south to be this. Stark nearly loses his job for doing it too well.
In Mercedes Lackey's Heralds of Valdemar books, it is built into the Heraldic system that the King or Queen always has a Monarch's Own Herald, ready to serve as trustworthy friend, confidant, and brutally honest advisor if needed. Part of their purpose is to call the Monarch out on anything questionable, stupid, or pointless they try to do. The breakdown of this relationship between Queen Selenay and Queen's Own Herald Talamir causes numerous political problems and plot points in the main time period covered by the books.
DS Barbara Havers is this to her partner, DI Lynley, on The Inspector Lynley Mysteries. Although it took her some time to earn the position, by the end of season two she can get away with saying things no one else could because she has earned his trust repeatedly over the course of their partnership, and though he might snap at her, she knows that's as far as it will go.
Londo Mollari in Babylon 5 is unhappily married to three wives: One (Timov) who unabashedly criticises him at every turn, and two others (Muriel and Daggair) who act nice to him in person while plotting behind his back. When he's permitted to divorce two of the three, Timov is the one he keeps even though she's given him no reason to like her. When she asks why Londo chose her, he explains that she was chosen because he would always know where he stood with her, unlike with his other two wives.
Revolution: Captain Jeremy Baker is this to General Bass Monroe.
All of President Bartlet's senior staff on The West Wing are fully capable of speaking truth to power; it's absolutely necessary, given who they're advising! Leo and Toby tend to give out the most unmitigated criticism, but Josh, Sam, CJ and even Charlie know not to hold back when the President needs a clear and unvarnished analysis of the situation at hand. Will has difficulty with this at first - in fact, he's given a Secret Test for it by Bartlet, and fails - but gets better at it as he settles into his new senior staff role.
Baron Wulfenbach in Girl Genius states early on that he prefers his men criticize him when possible, rather than see flaws but be too afraid to voice them.
Also, Agatha and Gil seem to prefer to have advisors who know how it is and aren't afraid to tell them off as well, Agatha with Von Zinzer, while Gil nearly always works with close friends rather than minions.
Italo Balbo, The Dragon of Benito Mussolini, who didn't trust the Germans and advised Mussolini to continue with the alliance with France and maybe build up an alliance with UK as well. Mussolini refused and Balbo answered with "You will all wind up shining the shoes of the Germans". Guess what Mussolini's last job was.
