In Assassin's Creed games, the Heralds always speak out against the Assassins even if you do your best to avoid civilian deaths. However, this is easily solved with simple bribes.
Jodie Holmes, the protagonist of Beyond: Two Souls, can potentially end up becoming one, being pursued by both local police and the FBI, to the point that every single cop in the state may potentially be called in to apprehend her.
Ragna the Bloodege is very much hated by the world, to the point where half of the cast are trying to kill him. This is justified though because, Jerk with a Heart of Gold he may be, he is also a wanted terrorist who has gone around destroying government facilities and cutting down any soldiers that stand in his way. There's also the little fact that he has a legendary Artifact of Doom that everybody and their mother wants to take from him.
Bang Shishigami tries very hard to be a Shonen action hero and is motivated purely to restore his fallen homeland. He even shows mercy to his enemies. However, because of his Large Ham and Hot-Blooded attitude, he's mostly seen as a crazy old man by most of the cast. Although, there are a few people who do respect him.
The Borderlands series plays with this trope in a rather interesting way:
The protagonists of the first game, Borderlands, start as treasure hunters and thrill-seekers and happen to rid part of Pandora of its most dangerous bandit leaders along the way to the Vault, being praised as heroes by the inhabitants. That doesn't prevent Captain Steele, the Crimson Lance leader, to publicly call them dangerous outlaws, but no one else seems to care.
In Borderlands 2, more treasure hunters and thrill-seekers join in, and are quickly hunted by Handsome Jack, a villain of otherworldly proportions who doesn't hesitate to publish bullshit news about them burning orphanages or strangling kittens, and this time he has an audience buying his shit. Luckily for the protagonists, they still have allies not believing him.
Come Borderlands: The Pre-Sequel!, that lets you see the events between the two previous games from Handsome Jack's perspective. There you learn important things: Jack wasn't the worst boss Hyperion ever knew, far from that; his first motives were rather understandable, to open a Vault for riches and to save all the inhabitants on Elpis from certain death by Kill Sat. While he had already committed various highly questionable actions by that point (including turning his daughter into his personal supercomputer) it wasn't until Moxxi, Roland and Lilith attempted to assassinate him and his Vault Hunters that he truly became the lunatic from the second game and that they were pretty much responsible for the events of 2.
In BoxxyQuest: The Gathering Storm, Anonymous is Catie’s loyal protector, fighting to save the Internet by her side, yet because of the Fantastic Racism against 4chan users, pretty much everyone else distrusts him, assumes he’s secretly up to no good, and blames him for anything that happens to go wrong.
In City of Heroes, there is a Story Arc where you become a Hero with Bad Publicity. You get framed for a crime and have to collect evidence that will clear your name, all the while being chased by the Malta Groupp and their Demonic Sappers.
In the first Command & Conquer at least, GDI. Nod's Greg Burdett, a respected journalist, would help them fabricate news stories about GDI slaughtering villages and burning down orphanages. Nod's mainline troops would also regularly partake in a little bit of the random slaughter, usually so they could make it look like GDI did it. This was also the entire point of the last couple of missions of Nod's campaign, in which you were working to hijack the GDI Ion Cannon to destroy a landmark (your choice), framing GDI for the attack. Meanwhile, in the GDI campaign, this is played with. It looks like Nod's media campaign has brought UNGDI to the brink of being disavowed by the Security Council, with funding being suspended while investigations are made... and then, when Nod launches a major offensive, it is revealed that it was a trick by the GDI leadership, taking advantage of Nod's media edge to bait the Brotherhood into striking before properly building up its strength. You still have bad publicity, but it wasn't so bad as it looked to you or Kane.
Adam Jensen in Deus Ex: Human Revolution was hit with this in his backstory. When Adam and his SWAT unit encountered a belligerent teenager with augments, he was ordered to take a kill shot because subduing the kid nonlethally would have been too much trouble thanks to his augments. Adam refused to take the shot and another SWAT commander did it instead. Adam quit the force in disgust. His superiors were upset by this and doctored his psyche profile to make him look like a violent borderline lunatic as payback. In the present, there are still rumors that Adam was fired from SWAT for that incident when he actually quit. Fortunately for Adam, the private investigator that David Sarif had looked into Adam's background before hiring him read between the lines of the profile and saw it for the fairy tale it was.
DmC: Devil May Cry shows a newscast of a reporter claiming Dante to be a terrorist from his "attacks" when really it's just damage caused by the fights in the parallel world, Limbo, carried over to the real one, however, humans can't see the monsters so they pin the blame on Dante. Justified since the news network is being run by those same monsters.
The Warden, in Dragon Age: Origins, is left with this reputation after the first battle of the game. Loghain spread the rumor that the Grey Wardens abandoned and betrayed everyone in the battle, which in point of fact is what Loghain himself did, and the Grey Wardens themselves were almost obliterated in the fight — only two remain alive in the entire kingdom. The trope is somewhat played with, however, because very few people genuinely believe that the Wardens are guilty.
If you choose the Human Noble background, your family's political enemies try to paint your family as rebels and traitors. However, when you visit the Landsmeet the other nobles make it very clear that everyone knows your family are staunch royalists and the bad guys full of crap.
By the end of the events of Dragon Age II, Hawke has become a legendary but controversial figure because s/he was at the center of an event that sparked a global conflict.
At the beginning of Dragon Age: Inquisition, the player character is the only one to survive an explosion that killed hundreds of people, including the Divine, and who everyone believes is responsible. After the prologue, some people start believing the Inquisitor has been chosen by their god to save the world, but many continue to think the Inquisitor is guilty for the first third of the game.
The DLC Trespasser takes place two years after the Big Bad was defeated and there has been an increasing backlash against the Inquisition (and the Inquisitor themselves), which many believe is power-hungry and on the verge of invading nearby countries. Subverted in that it's revealed the organization had been infiltrated by various spies and was falling to corruption after all, although this wasn't known to its leaders or critics at the time. Additionally, Dalish elves believe Fen'Harel is the god of deception who was responsible for locking away their other gods and dooming their civilization. In truth, Fen'Harel was leading a rebellion against the other gods, who had become slave-owning tyrants, and ended up locking them away to keep them from destroying the world. It is true, however, that he was responsible for their empire crumbling.
Dyztopia: Post-Human RPG: Downplayed with the protagonists, who are fugitives due to defying Zetacorp and are painted as terrorists by the media. However, when Detritus makes his case on Sho's show, most of the audience sides with him, much to Sho's dismay. After Morgalia blows up Vulcanite's mine and frames the party for it, they lose a lot of the popularity they built up, though Zazz notes that many still sympathize with them.
In The Elder Scrolls series, Meridia is a Daedric Prince whose sphere is obscured to mortals, but is associated with Life Energy, Light, and Beauty. She, in different ways, manages to be both this trope and a Villain with Good Publicity. Most of Tamriel is skeptical, or at least cautious, toward Daedra in general (especially after the Oblivion Crisis at the end of the 3rd Era), and some groups, such as the Vigilant of Stendarr, actively oppose any and all Daedra regardless of intention. Meridia, however, still undertakes actions on behalf of mortals despite this and sometimes has to work through a proxy (like Sees-All-Colors in Online) for groups that would never collaborate with her willingly.
James Parnell in Evolve has this as part of his backstory. He was the leader of a mercenary group that dedicated itself to helping the little guy, often against the will of Hub. When a rescue attempt when wrong, the media blamed him for the loss of his own ship, the other ship, and every member of both crews.
EXTRAPOWER: Attack of Darkforce: When Ruritia is encountered in a district of Tokyo, the entire town has already turned against her. The rookie Hikari Warrior is stationed there to protect the hiding place of the Seven Colour Princess, and the local public has put all the blame on her for the damage caused when the Yami Clan shows up to find her. And now that Undata and his Clay Kids are lobbing missiles and laser blasts everywhere, even more blame is put on her head. It's quickly decided that the only choice to make is to prematurely release the Princess from her slumber and go on the run.
Entirely possible in Fallout: New Vegas. Because your karma (how good or evil you are) is factored separately from your reputation (how much people like you) it's very, very possible to end the game with the highest karma possible, and every single faction hating your guts.
In the "Cosmos in the Lostbelt" storyline, even though the heroes of Chaldea saved the world several times, the Mages Association fires and brands them criminals just because their actions threaten to break the Masquerade. It is also because nobody is aware of their time traveling adventures, so the Mages Association thinks they haven't done anything significant and are a waste of resources.
Xiang Yu could see the future and did everything he could to save others from their fates, no matter how dirty the method. But because he never bothered to explain himself, everybody except his wife, Yu Mei-ren, hated him. When he died, he did not ascend to the Throne of Heroes because nobody believed he was a hero. It isn't until the immortal Yu Mei-ren finally dies and ascends to the Throne, allowing her to share his side of the story, that he ascends.
Ramza in Final Fantasy Tactics. He gets branded as a heretic for pretty much telling the bad guys to stop doing bad things, and is STILL remembered as a villain after the game is over. It eventually stops and it's implied he gets the recognition he deserves... five hundred years later.
Orran Durai also gets this as he attempts to tell Ramza's story to the public and the church brands him as a heretic as well, and has him burned at the stake and hides his history... until it is found hundreds of years later and clears both of their names.
In Final Fantasy X, Tidus and later Yuna develops a case of this for not going along with temple traditions.
Woman: You heathen. Old woman: Stay away from the summoner. Young girl: You're a bad man!
Yuna also gets hit with this in Final Fantasy X-2. If she returns an artifact to New Yevon, the Youth League hate her; if she gives it to the Youth League, New Yevon hates her. Either way, she gets either insulted or attacked by one side for a good chunk of the game.
Poor Basch from Final Fantasy XII is hated so much as The Kingslayer (who's also allegedly responsible for Dalmasca's occupation) that two of your other party members attack him physically on sight. Most people also believe he's been executed for his crime, as a result of a Death Faked for You.
In Final Fantasy XIV, the Dark Knight job is regarded with suspicion and fear in its homeland of Ishgard due to its use of The Dark Arts in a society steeped in religious dogma, as well as a reputation for ruthlessness and a history of going after people in positions of leadership that otherwise make them above the consequences for their crimes. This extends to the origins of the Dark Knight, wherein an Ishgardian knight sacrificed his position and reputation to slay a Pedophile Priest who had, to that point, managed to keep his crimes secret and had a beloved reputation among the citizenry.
Fire Emblem: Genealogy of the Holy War: During chapter 2, it's revealed that Sigurd's family have become implicated in an attack on the king, staining his reputation and causing him to be viewed as a ambitious warmongerer who would do anything for power. Of course, while these rumours are going around, Sigurd is in the process of fighting a veryill-advised war attempting to liberate a friend from being a political prisoner, so the bad publicity isn't entirely without merit...
Fire Emblem Fates: This happens inevitably with the faction you don't choose to side with. Granted, while the royal siblings don't hold too many hard feelings against Corrin once the war is over, the rest of the common populace isn't that forgiving:
In Birthright, Corrin is reviled in Nohr for their betrayal even as he sided with Hoshido to dethrone King Garon. This has eased up somewhat come the end of the route, where King Leo and Camilla seek to help clear up any misconceptions about the Hoshidans.
Corrin is hit with this the hardest in Conquest, where their decision to side with conquerors to protect their family gets him utter indignation in Hoshido, to the point that upon returning to Shirasagi, Hoshido's capital, you're greeted with the Hoshidan populace jeering you as a traitor. It's only the end of the route that Queen Hinoka makes abundantly clear that while she and Sakura forgive Corrin for their efforts to salvage the situation and will work to clear up any remaining hatred, the process won't be easy and it isn't safe for Corrin to visit Hoshido so hotly fresh after the war.
In Genshin Impact, Eula of the Knights of Favonious is a good person and is even a captain of the order, but due to being a member of the Lawrence clan most of Mondstadt refuse to have anything to do with her, occasionally driving her to drunkenness.
In Golden Sun: Dark Dawn's recap of the first two games, what little mention there is of Felix's actions openly casts him in a bad light, and the Fire Clan's are never explained at all; (though the latter weren't particularly heroic to common knowledge).
It doesn't affect the overall gameplay, but the main character of the first Hero of the Kingdom installment has the option to desecrate a few graves in order to plunder treasure from them. This causes their 'hero' rating to drop several points, indicating that they have temporarily become this.
Subverted in inFAMOUS. The player character starts out with bad publicity because he was the delivery boy who carried the immensely destructive Ray Sphere into the heart of the city, where it exploded; but as time goes on (and if you choose to play as a good guy), his publicity gets much better.
Jak and Daxter are constantly painted as bad guys by those in power, culminating in Veger having them kicked out of Haven at the start of Jak 3: Wastelander, even though they both saved the city before.
In most locations, Helena is worshipped as a benevolent goddess. In Zamaste, Helena is considered a traitor whose romance with a human caused Zamas to hate humanity, although this viewpoint ignores the fact that he felt this way even before learning of Helena's love life.
Knight Bewitched: Gwen is a witch, but she is working in a permanent cure for the Bog Fever afflicting people who visit the Underbog. Despite this, the city is terrified of her for no particular reason, and she is being accused of massive crimes.
The Jedi Exile is subject to this constantly, having been indirectly responsible for the accidental destruction of Peragus II during the prologue, which several characters across the game remind them means almost-certain doom for Citadel Station over Telos because Peragus was the station's only fuel source. The Exile was also one of the Jedi who joined Revan during the Mandalorian Wars, where they gave the order to detonate a superweapon over Malachor V, wiping out all life on the planet and in orbit and ending the war. When the game begins, the Exile returns from their ten-year long self-imposed exile on the Outer Rim, having been banished from the Jedi Order for their actions during the war.
The Jedi Order are also subject to this in the second game, and have been forced into hiding between this and a new Sith threat that is able to target and eliminate them without ever revealing itself. It's explained that as a result of the Mandalorian Wars, the Jedi Civil War and Revan and Malak's attempted takeover of the galaxy, most common people consider the Jedi and Sith to be indistinguishable from each other and little more than crazed zealots bent on destroying the galaxy over their opposing ideologies. There's even a bounty for Jedi set by the Exchange, meaning you spend half the game fighting off a variety of hunters hoping to collect.
Lemeza Kosugi in La-Mulana 2, thanks to what happened at the end of the first game. He saved humanity, but had to destroy a world heritage site in the process. The public either doesn't know or doesn't believe his reasoning, so he's been on the run from Interpol.
At the end of The Legend of Heroes: Trails of Cold Steel, Giliath Osborne has managed to break the curse of Ishmelga-Loge that has been plaguing Erebonia for a thousand years, which was responsible for the Dark Dragon Zoro-Argula, The War of the Lions, and the Hamel Massacre. Unfortunately, between the fact that the existence of the curse not being public knowledge and setting things up so that the curse could be broken involved a decade of work as the Evil Chancellor which culminated in a war of aggression on false pretenses that spread to involve half the continent, Zemuria as a whole will remember him as one of the greatest villains in history.
Subverted in The Legend of Zelda: A Link to the Past; after Link saves Princess Zelda's from Agahnim's clutches, Agahnim put a false bounty on Link's head accusing him of kidnapping Zelda. Most Kakariko Villagers are still friendly to Link, with one outright saying she refuses to believe Link would do such a thing. Only two villagers are actively hostile enough to sic the guards on Link if he tries to talk to them, with a third merely being unsure and keeping his distance.
This trope can also happen in The Legend of Zelda: Link's Awakening, although in this case, it really is justified. It is triggered if you make Link steal any item from the store by careful maneuvering around the shopkeeper while carrying one of the items. Should you decide to do it, your game file will be permanently renamed to THIEF, and everybody in the town will treat you accordingly, and if you return to the shop after stealing an item, the shopkeeper uses magic to shock you to death. Yikes. Still, it is pretty hard to resist doing this in-game, since the bow in the game is sold at the ridiculous price of 990 rupees (the rupee cap is at 999), and it takes a looooong time to save up that amount of money.
Wolf Link in The Legend of Zelda: Twilight Princess. Outside of the Twilight, he's feared as a monster. Inside of it, he's invisible so he gets no credit for his heroic actions. Thankfully, Link also has a human form in which he can be viewed heroically.
In The Legend of Zelda: Breath of the Wild, the older generation of Zora hold Link in contempt, largely because they blame him and the Hylians in general for digging up the Guardians and Divine Beasts that Calamity Ganon possessed to devastate Hyrule, which caused the death of their beloved princess Mipha killed in the process. The younger Zora, in contrast, either weren't alive when all this happened or were Childhood Friends with Link and thus have no reason to hold him responsible. And the older Zora eventually soften their views once Link subdues Divine Beast Vah Ruta.
Kazuma Kiryu, and understandably so - he's a former crime lord, an ex-con, frequently gets into public fights, has a face like he'd beat the shit out of you if you looked at him wrong, and doesn't care about glory so he does nothing to fix his bad PR. To the public, he's pretty much Public Enemy No. 1; only his close acquaintances know that he's actually a kind and heroic fellow. In 5, this forces him to relocate to a different city since Park only agreed to give his orphanage some much-needed funding and a celebrity career for his daughter Haruka if Kiryu agreed to disappear somewhere, and in 6, once the connection between him and Haruka is made public, she chooses to run away so as to not soil the reputations of the orphans by association with her.
Masayoshi Tanimura is infamous in Kamurocho for being a Dirty Cop who gambles, takes bribes, and extorts money from various businesses around town. It's to the point that he's earned the moniker "The Parasite of Kamurocho". What's lesser known is that he only takes cash from businesses that illegally hire immigrants, and uses his position to protect said immigrants where the law otherwise wouldn't. The cash he earns then goes into the Asian Gateway program, which helps immigrant children whose parents have been forcibly deported. He's every bit the dirty detective that the public suspect, but it's not without a good motive.
The politician Ryuzo Tamiya from Yakuza 3 is more dedicated than anyone to protecting Japan, but his gruff demeanor and his stance on military and defense make him extremely unpopular among the people.
Masato Arakawa from Yakuza: Like a Dragon is one to the yakuza world rather than the public. He's considered a greedy coward and traitor for selling out the Tojo's secrets to Ryo Aoki. Turns out he did so with the explicit permission of the Tojo chairman to keep Aoki from going after other families.
Ryoma from Like a Dragon: Ishin! gets a double dose of this trope. Firstly, he is considered a wanted fugitive in his native Tosa after he assaults two Joshi soldiers and then is framed for his adoptive father's assassination and his subsequent escape from the province. Then, in his search for the killer, he joins the Shinsengumi, a Bakufu-backed special police force with a reputation for ruthlessness and violence feared by the people of Kyo as the "Mibu Wolves". The latter one becomes downplayed as Ryoma builds up reputation in the various districts- NPC chatter will increasingly become people talking about how maybe things are changing for the better if he's part of the Shinsengumi or talking about the heroic acts he's performed.
Commander Shepard in Mass Effect 2, what with the Illusive Man resurrecting and manipulating him/her to save the galaxy with a Cerberus logo on his/her ship, s/he has to deal with this problem throughout the game. On the one hand, the civilians who recognize him/her love Shepard, though there are still some who feel betrayed by his/her long absence and rumors about his/her working with Cerberus. But those who knew him/her personally range from being leery of his/her new connections to outright enraged that s/he would associate with them. It's heavily implied that Cerberus invoked this with strategic information leaks to keep Shepard away from people who could counter Cerberus' efforts to manipulate him/her.
Mega Man Zero: Everyone calls him a legendary hero, but only a few know that there's something more benevolent to Zero's "extremist" actions. This isn't really explored until the fourth and final game since all characters that Zero interacts with prior to that game are Reploids who see him as a champion to their cause. It was in the fourth game that a colony of human refugees are introduced, and this trope is in full force.
As of the end of Metal Gear Rising: Revengeance, Raiden appears to have become this. Going on a bloody rampage through the city of Denver and butchering legions of cops (Dirty Cops, yes, but cops nonetheless) on a mission to dismantle the biggest Private Military Contractor in the world will do that.
Metal Gear Solid 3: Snake Eater has an especially tragic one that is also posthumous with The Boss, who undertook a mission as a Fake Defector. But as soon as something went wrong, she was scapegoated by the U.S. government so they could save face, and she went along with it, both to prevent World War III and out of continuing loyalty to her country. From the start, she knew that her favorite student would kill her and she would be remembered in death as one of the most despicable traitors and war criminals in recorded history. Later games reveal that the mission wasn't even about saving face; the government wanted The Boss dead from the very beginning because they were afraid of her.
Marina from Mischief Makers takes flak from the evil double's paper-thin disguise.
Averted on Phantasy Star Online 2. During the final chapter of episode 2 Luther has the player character named as public enemy number 1 after the player character comes dangerously close to destroying the plans he has had in motion for decades. However due to the player character's status as the up and coming hero of ARKS, very few members of ARKS and civilians are convinced and as a result, he has to rely on a body-hijack command programmed into each ARKS member to get them to try to take the player character down instead.
Marona, the protagonist of Phantom Brave. She is quite possibly the nicest person in the whole world, but almost everyone fears and hates her and calls her "The Possessed One" because of her ability to communicate with phantoms. People routinely send her nasty letters or write articles in the paper where even the good things she does get nasty spins; she is blamed for things she had nothing to do with, and some of the people who hire her cheat her out of payment for various reasons. She keeps soldiering on, smiling and waiting for the day when everything is going to be okay. Thankfully she does gain friends and respect from some people, and in the end everyone respects her for saving the world, including the nasty columnist in the paper.
In Pokémon Black and White 2, Old Team Plasma is this, consisting of those Plasma members who truly believe in Pokémon and humans living side by side in harmony, but unsurprisingly, they have a lot of work ahead of them to atone for Team Plasma's crimes in Black and White.
The local gang Team Star is considered by everyone to be a bunch of bullies. However, once you meet them it's revealed that they were actually Bully Hunters who got a bad rep after they made the kids who bullied them drop out and the school's previous administration covered the whole thing up, causing the members of Team Star to cut class in protest which allowed rumors about them to persist unabated.
The Legendary Pokémon Ogerpon from the Teal Mask expansion was vilified by the people of the Kitakami region after it tried to avenge its Trainer who was killed by the Legendary Trio known as the Loyal Three. The villagers, who only saw a rampaging ogre randomly attacking three Pokémon, assumed it was the bad guy and worshipped its victims who they believed were defending the village. The one man who knew the whole story was branded The Heretic and made an outcast when he tried to tell people.
While Aeyr isn't a straight-laced hero fighting for higher ideals, he does risk his life to defend Asala for Amalie's sake. When he becomes a Revenant, everyone in Asala, including Amalie, sees him as a threat and tries to kill him. This causes Aeyr to completely abandon Asala and give up on playing nice with society.
Mia tries to be a good leader to the Honneleth refugees, but due to numerous setbacks, the refugees become impatient and lose trust in her. When she reveals that she hid the truth about Vanessa's experiments from them, they angrily demand that she takes them back to Asala, despite how Kakuri is obviously safer. When Mia overthrows Vanessa and takes over Asala, most of the population riots against her rule, since they fear a regime change. Ironically, Vanessa points out that Mia's least heroic act in the game, sending Aeyr on a suicide mission to kill Gauron, would probably cause history to recognize her as a heroine.
Alex Mercer in [PROTOTYPE] is treated as a villain. And understandably so: not only is he a carrier of The Virus who runs around Manhattan eating people, he looks like and has the memories of the scientist who released The Virus in the first place. Nevertheless, he's grown a conscience by the end of the game and ultimately performs a genuinely heroic and selfless act... that is, until[PROTOTYPE 2]comes along.
Quest for Glory IV starts out like this, due to suspicious townsfolk who are fearful of strangers and especially anything to do with magic, although the hero will gradually win their trust by helping them out.
Ratchet: Deadlocked has both a subversion and a rare villainous example of a hero with bad publicity. The game's Big Bad, Gleeman Vox, wants to promote Ace Hardlight as the starring attraction of his game show Dreadzone, and his company Vox News goes well out of its way to slander and ridicule Ratchet to preposterous levels. However, it quickly becomes apparent that no one is buying it, as the only Dreadzone merchandise that's selling are the "Fuzzy Lombax Ears" meant for toddlers. Meanwhile, Ace's utter lack of charisma means he suffers from X-Pac Heat, and as a result Vox can't even give his merchandise away. When Vox tries to get Ratchet to sign on and become his new star, he claims that the early slander was just playing up a "bad boy" image. Ratchet, naturally, doesn't buy it.
Refreshingly subverted in Spider-Man (PS4). Despite both Jameson's podcast and Osborn's Mayoral Office running smear campaigns against him, the people on the street seem to recognize the good he does, with one woman him calling him, "everything I love about New York". He can even take selfies and high-five people on the street, which actually provides the "Spider-Man About Town" trophy after he interacts with ten different citizens. He also has a good number of more active fans, like an impersonator who put on a Spider-Man costume in hopes of helping, and Miles Morales.
Tassadar has a bit of a publicity problem in StarCraft due to his alliance with the Dark Templar and the Terrans. Arcturus Mengsk used to be one too, back when the Confederacy was in power. Jim Raynor has been one ever since the Dominion rose to power.
Star Stealing Prince features a variant, with Prince Snowe starting off well-loved by his subjects. However, early in the game he comes so close to death that it ends up breaking a spell cast on the entire kingdom, and one of the many side effects is that Snowe's subjects (aside from a select few in the court) don't remember him, but instinctively don't like him (probably because he's part of the original incredibly selfishroyal family who cast the spell on them in the first place).
Georg Prime of Suikoden fame is frequently accused of committing regicide against the Queen of Falena. It's true, but she WANTED him to do it, as it was the only way to keep her from using the Sun rune (which was driving her insane) to wipe out the entire country.
Tales of Vesperia's infamous YuriLowell is officially a criminal due to various factors (a lot of which are a product of his bad luck). Yuri...doesn't care. He's actually kinda pleased to find himself with wanted posters. Though he really did commit the crimes he's accused of (well, at least most of them; one of them was a misunderstanding). His friends aren't so amused, especially when it means they have to flee the inn they are staying at to avoid a confrontation.
Valkyria Chronicles III: Kurt Irving and The Nameless can give Ramza a run for his money. They are supposed to do the dirty jobs that the official military won't, and at one point was branded traitor (and possibly heretic). But they finally have their name cleared, even if they must live in obscurity for the rest of their life.
Depends if you're talking about an individual level or group level. Individually, most are nothing more than people caught in a bad situation or simply got shanghaied into the unit. By comparison; two characters are actually Lanseal graduates (the game's equivalent of West Point), one of which graduated with honors. (And that's not including the volunteers.) As a group, the unit's bad reputation has more to do with the fact that its commanding officers keep them on hand and use them explicitly for wet works than anything they actually do.
Valkyria Revolution has the Five Grand Criminals, who started a war with The Empire and managed to kill thousands of people in the process. This is actually true, but they needed the war to rescue their Cool Teacher, who had been kidnapped by the empire; starting a war was their only ticket to save her. Their actions, however, also benefited Jutland in that after the war, Jutland became one of the richest nations in the world. A researcher at an academy 100 years later wants to prove their innocence, while a descendant of one of the people who know about the conspiracy wants to keep it secret because it's what the Five Grand Criminals would have wanted.
