In Fist of the North Star, Kenshiro never hesitates in saying he follows the path laid by those before him when about to instill an asskicking on someone. Specifically, Rei, Toki and Raoh will always be shown.
To give you an idea: Nanoha Movies exist in-universe. Unfortunately these are also TSAB propaganda, so certain characters don't get de-famed in story even if they really, really deserve it— such as Admiral Graham and his involvement during Book of Darkness incident.
Quant, a Ranker from Tower of God, who only appeared in person in one story arc where he revealed himself as rather buffoonish and a manchild, must be one of the most popular characters in the Tower since his face is on nearly everything from public service announcement posters over chocolate bars to strength measuring devices.
Kogoro Mouri of Detective Conan has gotten the reputation of a Great Detective after one season on the strength of ConanEdogawa's behind-the-scenes work and is often recognized by face or name by those around him. Frequently, when Kogoro's name and/or vocation enters conversation, it will provoke reactions of shock in the (not-yet-known-to-be-a) murderer (and/or others with something to hide). Although Kogoro almost never notices, Conan usually does—and this is often his first clue that something is amiss.
Lina Inverse goes beyond world-reknowned in Slayers. In the anime she finds out several of the epithets people know her by, which she's none-too-pleased with as they make her sound more like a blood-crazed psychopath than a great and wise mistress of arcane forces (to be fair, they're more accurate than her own self-image). One that particularly irks her is "Dragon Spooker", because supposedly dragons will step aside and let her pass mid-rampage rather than risk dealing with her. Then, later, a dragon in the middle of a town-destroying rampage catches a glimpse of her face and tries to nonchalantly make an escape....
In Chrono Crusade, Mary Magdalene (not the Biblical character, but an orphan named after her) is a Post Humous Character who is very well-known among the Church Militant exorcists for her legendary holy powers and graceful demeanor, and is brought up enough that her name is practically an Arc Word.
One Piece: The Straw Hat Pirates become increasingly famous as the story goes on, eventually hitting the point where the mere mention of their names strikes fear into most pirates, criminals, and citizens. Bounties serve the general story purpose of making sure that all of the setting's pirates are well-known.
There's also Gold Roger who is well known as the "King of Pirates".
In Naruto, this happens all the time. Any ninja famous enough to have a nickname is generally the subject of legend. Just remember how the First Hokage is worshipped as the God of Shinobi, or how the White Fang was said to be even more of a legend than the Sannin, who were the subjects of lore in their own right. And then I haven't even mentioned the Yellow Flash or Uchiha Madara yet. There's a whole list of (mostly dead) characters who have achieved a legendary status.
Interestingly enough, Obito only remembered of the White Fang that he had died as a hero for the village; Clearly Konoha's Academy only teaches the parts of the legend it wants its students to know about
The Fairy Tail Guild in the country of Fiore. They pride themselves on being one of the most known guilds around.
In Saint Beast, everyone in heaven knows of Judas, even if they've never seen him. He needs no introduction whenever he meets someone new.
In Berserk, the Band of the Hawk became Midland's national heroes through their efforts in the One Hundred Years' War against the Tudor Empire. After their banishment and eventual demise during the Eclipse, which was deemed as a mysterious disappearance by the populace, the people never forgot their actions and only hoped for the Hawks to return to save their kingdom from a new threat.
Kenshin is best remembered as Hitokiri Battousai, and the revelation of who he is enough to make a cold blooded killer break into sweat.
From the very beginning, Sailor Moon is so popular with the public that throughout the series you can see plushies, figurines, and even costumes made in her likeness (along with the other Senshi). Her predecessor, Sailor V, is even more legendary, being greatly admired as a heroine of justice; she is talked about frequently before she is formally introduced, and there was even an anime being made about her. When Sailor Venus finally joins the team, Sailor Moon is a full-blown Fangirl of V's.
The most famous captain of the current generation is Byakuya, even commoners in the Rukongai know who he is. Ginjou explains it's because his extremely high social rank combines with his extremely high military rank to make him far more well-known than any "normal" captain or high-ranking aristocrat would be by themselves. Byakuya himself once implies that this creates an enormous pressure on him to be the role-model that all Soul Society must look to.
When Ichigo first arrives in Soul Society, he discovers that just mentioning he was trained by someone called Urahara sends shock-waves through his listeners. Not only was Urahara someone who was infamous for being an exiled captain (later proven to have been framed by Aizen), but his long conflict with Aizen and his status as the most intelligent person alive means that not only has everyone heard of him, but everyone relies on him - even the people who don't want anything to do with him need his help. He's even a legend among the Royal Guard.
Urahara: "Hello, everyone! Calling all Captains of the Gotei 13! And their respective Lieutenants, of course! This is Urahara Kisuke! Some of you may not have met me or be familiar with my name but I hope you'll forgive me if I skip the introductions..."
Shinji: "Heh. As if anyone wouldn't know your name, dumbass!"
In "Schippeitaro", the young man will adventure until he gets this.
Beltorey: This incident is going to spread like wildfire, and whether for better or worse, this small note The official number then eight-person clan is now officially on the map.
In Pony POV Series, Apple Bloom became this in the Dark World by working for years to free Sunnytown from their curse and succeeding (it helped Discord cursed her the same way, though Applejack broke the curse after she succeeded by her request). For this act, she's remembered as Saint Applebloom of Sunnytown, especially by her descendants. Applejack recently gave her another boost of fame for revealing her spirit helped free her from Discord's control.
A New Chance Series: After gaining Latios and Latias as Pokemon and using the former in the Johto Silver Conference, Ash gains the fame, fans (especially Max) and recognition he failed to achieve in canon, with rivals and enemies alike knowing him as the kid with the Latios.
The Twilight Child: Happens when the Mane Six travel to Canterlot for the Hearth's Warming play. An angry stage director confronts them when they arrive, but quickly changes tack when he realises who they are, or who Fluttershy and Rarity are, at least. He then allows them full reign in "his" theatre. Rarity takes full advantage of this.
Films — Animation
In Kung Fu Panda, the Furious Five are legendary kung fu masters famed across China. At the end of the film, the title character himself becomes a legend as the Dragon Warrior.
Norrington: You are without a doubt the worst pirate I have ever heard of. Jack Sparrow: But you have heard of me.
The Mystery Team was once a well-respected and popular part of their town.
In The Dark Knight, Batman takes the blame for Harvey Dent's murders, and is subsequently hated by the people of Gotham. In The Dark Knight Rises, he gets his good name cleared, and in the end a statue of him is erected.
Captain Dax, at the end of Starship Troopers 2: Hero of the Federation. Played for irony, as the Federation trumpets him as the champion of the very ideals he was shown to be very cynical towards in life.
In J. R. R. Tolkien's The Lord of the Rings, they hear the tales of Beren and Lúthien at Rivendell. Frodo and Sam discuss, on the way, whether they would get such a story, and they are deeply moved when they are rescued from Mount Doom and actually get to hear "Nine-fingered Frodo and the Ring of Doom".
In James Swallow's Warhammer 40,000Blood Angels novel Red Fury, Rafen looks at the carvings about the tomb, recounting the deeds of a Blood Angel who had actually entombed Sanguinius's body; it inspires him to carry on. Later, Turkio considers how he, a mere line-brother, will not be remembered in stories, but still carries on.
In Lee Lightner's Warhammer 40,000Space Wolf novel Wolf's Honour, the skald, Morgrim, attends all that happens to recount it in song. When Mikal realizes he overheard him talking to his unconscious superior, he angrily demands to know how Morgrim will tell it; Morgrim declares that he will say that a hero paid his respect to his lord before battle, and Mikal refuses to believe it, thinking Morgrim will remember him as a failure. Morgrim assures him that his lord had felt the same way on many an occasion.
In Terry Pratchett's The Last Hero, the heroes' motivation is that their attack on the gods will be remembered; they even drag along a minstrel to be sure of it. And in the end, the minstrel gets them to save the gods by pointing out if they destroy the gods — and the world — no-one will be around to remember. And then he recounts the story in song.
Oh, it's better than that: he invents heavy metal.
In Jim Butcher's The Dresden Files novel Dead Beat, Luccio gives this as a reason to insist on Harry's becoming a warden; he's fought more evils than many wizards much older than him, and it's known. In later books, Harry notes that he thinks of it as part Shrouded in Myth, because he remembers how close some of the things were. He doesn't seem to realise that only just raising a zombie Tyrannosaurus Rex is still a nigh-on Godly feat.
Harry is also The Dreaded to various supernatural baddies. At one point a Red Court Vampire who also happens to be one of the Court's most deadly and skilled assassins turns and runs screaming at the sight of Harry.
Harry manages to go from a relative unknown in the first book to being recognized on sight by more and more people after only a few books. It helps that there's generally a gap of about 6 months to a year between each book, which is plenty of time for word to spread.
As of Manslayer, we know that Felix's brother Otto has been publishing the journals he sent home for safekeeping (to act as notes for the eventual epic). And they have proven to be popular, if taken for fiction in some quarters, and disliked by those "slandered" by their portrayal.
In Wen Spencer's Endless Blue, Hardin tells Mikhail that immortality is when people know your name millennia after your death. Mikhail later threatens to eradicate all record of him if he does something.
In The Belgariad, the heroes exploit this: although they were careful to never mention the thief or what he stole by name for a time, they get all the minstrels to start telling certain stories. This creates such a clamor that the bad guy can't pick them out of the crowd.
A major theme of Ben Counter's Daemon World. The narrator recounts legends rather than tell the straight story of anything. (Partly because that way contradictions can be introduced.)
In Henry Zhou's Warhammer 40,000 novel The Emperor's Mercy, Imperial Guardsmen are surrounded by Chaos forces and are fighting on, despite dying of hunger and disease. Roth tells Celemine that they had no choice but to stay with them. The commander hears and instantly wants to fight a last charge: they can get them to their ship and hold off the enemy — and that way, they can be remembered. (They are. In fact, their eighteen minutes defense of the ship is immortalized in a mural on Terra.)
Mercedes Lackey's By the Sword starts with the teen protagonist Kerowyn going on a rescue mission alone to save her brother's fiancee. By mid-book "Kerowyn's Ride" has become a popular song. Three-quarters of the way through everyone she meets seems to know it... and half of them cannot sing.
Kero gets off lucky compared to Kethry (her grandmother) and Tarma (her teacher). They had to deal with several, many of which were composed and consciously embellished (motivated by mere money? nonsense!) by one particularly irritating minstrel with a fixation on the latter.
Luke Skywalker and the Shadows of Mindor has several references to the pulpy, facts-optional dramas created around Luke Skywalker, one of which is plot-important. Luke does not appreciate these and the impressions that they give about him.
In Starfighters of Adumar, Wedge Antilles and Red Flight are sent to Adumar purely because they're famous pilots. In this case, at least, the pilot-happy culture did know what they'd actually done.
Professor McGonagall rightly predicted that Harry Potter would "be famous. I wouldn't be surprised if today was named Harry Potter Day. There won't be a child in our world who doesn't know his name."
Quantum Gravity: Zal is a rock star. He's also known for trying to bring together the elves and the demons, but for those who know it's more Infamous In Story.
In Dan Abnett's Gaunt's Ghosts story "In Remembrance", after taking Thuro out on a patrol rather farther than they should have, the Ghosts make much of his recognizing an ambush and fixing a flamer on the field. Thuro then goes on to commemorate them in a statue; the story is framed as an interview about that, his most famous work.
In John C. Wright's Fugitives of Chaos, Grendel talks of how Hesiod wrote of his mother and is not surprised that Amelia is shy about meeting her, her being famous and all.
In The Princess Series, the stories of the main characters (Snow White, Sleeping Beauty, and Cinderella) are as well known in their world as they are in ours. Played with as the versions of the story that are most well known are the Lighter and Softer Disney versions while what really happened is closer to the Darker and Edgier Grimm Brothers versions.
Patrick McLanahan from Dale Brown books experiences both this and The Greatest Story Never Told. While he is recognised as a hero for such events as the counterattack against the American Holocaust, there are also many of his world-saving missions that the public will never know about until he's dead if not years after due to being black ops.
In Connie Willis's All Clear, the men working at making Hitler think that Calais is the attack point are given instructions after D-Day after the observation that the rest of the army will get credit; they will be covered up.
The very first Conan story written, "The Phoenix on the Sword," opens with an epigraph from an in-universe historical text called The Nemedian Chronicles, which reads in part, "Hither came Conan, the Cimmerian, black-haired, sullen-eyed, sword in hand, a thief, a reaver, a slayer, with gigantic melancholies and gigantic mirth, to tread the jeweled thrones of the Earth under his sandalled feet."
David Gemmell's heroes usually become famous when songs are written about their deeds. Druss, Waylander, the Earl of Bronze and the Thirteen are remembered long after they are dead.
Ulric's big regret about Druss's death is that he will be cast as the villain of the stories that will be written about the siege. He did not know that his champion put poison on his sword and would have never allowed it but history will not remember it that way.
Ursula K Leguin's A Wizard Of Earthsea is explicitly described as being about him when he was young and not famed in story; in it, a friend declares he will make a song so his deeds will be rememember, but either he didn't or the song was lost. However, by The Farthest Shore, Ged is indeed famed.
"A one-armed smith killed the king of giants? There will be songs written about this!"
Jamie "The Kingslayer" Lannister is (in)famous throughout Westeros for killing Aerys "The Mad King" Targaryen, for being incredibly good-looking, and for being the best swordsman in the kingdom. He finds it rather annoying.
In Codex Alera, Aldrick ex Gladius often serves as The Dragon for whichever character is currently in control, and not as a clear antagonist on his own, but he is legendary throughout Alera for his famed skill with the sword. His duel with Araris Valerian, also legendary because of his skill, is still being talked about fifteen years later.
Much to his embarrassment, Prince Bahzell has his own ballad (The Lay of Bahzell Bloody-Hand) constantly added to by his "bard" friend Brandark. Unfortunately for Bahzell, Brandark set it to the tune of a popular drinking song, and News Travels Fast.
Katniss, Peeta and any other tribute who won their Game and thus survived due to the very nature of "The Hunger Games". Just like with reality show contestants in real life...
In Rick Riordan's The Heroes of Olympus novel The Mark of Athena, Annabeth is surprised to find, among tapestries depicting other famous events, the time she and Percy were kissing under a river.
Mary "Jackie" Faber, aka Bloody Jack: the common seamen of the Royal Navy call her "Puss-in-Boots", consider her a good luck charm, and practically worship the deck she walks on. Her fame becomes even more widespread once her friend Amy starts publishing her adventures.
In The Orphan's Tales Zmeya's tragic story is so popular people go mad from love for her, or like Oubliette try to follow her to the land of death.
In Spheres of Influence: Ariane proves to be this after her actions in Grand Central Arena, when she meets her first fan in the Arena, asking for her autograph.
In Rachel Griffin, Sigfried Smith is a celebrity at the age of fourteen for having killed a dragon. He also saved Roanoke Campus from a flying, flaming skunk.
After Arrow-Odd of The Saga of Arrow-Odd has returned from his very first raiding expedition that took him to Bjarmaland, almost everyone to whom he introduces himself asks in response asks, "Are you the Odd that went to Bjarmaland?"
As shown in semi-fictional form in Band of Brothers, Ronald Speirs used his reputation as a cold-blooded killer to his advantage. This was explicitly pointed out by Speirs to Lipton. In both the show and in real life, no-one is quite sure if he really was that much a stone-cold killer. On the other hand, given the stuff he is actually known to have done (his Crowning Moment Of Awesome being his run straight through a German occupied village... and then back) his rep really didn't need extra padding.
In the Doctor Who episode "Forest of the Dead", the Tenth Doctor is trying to rescue some humans who are stuck in a library being claimed by a colony of aliens. They don't care about the humans, and are going to kill them just to get them out of the way. The Doctor tells them "I'm the Doctor, and you're in the biggest library in the Universe. Look me up." They back off immediately.
Appears erratically throughout the series. He does, after all, hop through space and time and isn't actually universally known.
This trope backfires SPECTACULARLY on the Doctor during series 5 and 6. As a result of throwing his weight around, the Doctor has become Famed in Story as a Technical PacifistOne-Man Army who survived the Time War by wiping out his own people along with the other guys and generally seems to like playing God with the universe while being somewhat/completely bonkers — and the bad guys respond by not waiting around for the Doctor to "fall from the sky and tear down [their] world" and taking the fight to him instead, putting the Doctor's closest friends (and sometimes the whole rest of the universe) in the crosshairs as well. In the end, the Doctor has to fake his own death and go back to being anonymous in order to continue operating.
Star Trek's Klingons love immortalizing their great heroes in song; for example, Kahless.
Klingons being Klingons, they tend to shout "This day will be remembered in song!" at the drop of a hat. One gets the impression that they probably say it after a particularly good meal.
The crew of Voyager gains quite the reputation in the Delta Quadrant. Admittedly, it's not all roses; one planet had a museum exhibit in which the Voyager crew were a bunch of sadistic Nazis.
A Romulan senator meets Sisko and after listing off some of his accomplishments, vaguely insinuates he's unimpressed.
Moya's crew in Farscape has built up quite a few impressive exploits as a result of being chased all over the galaxy by bad guys. As a result, word has gotten around, though the stories are a bit... exaggerated, in some respects.
First, in "Suns and Lovers":
Borlik: You know, I heard he destroyed a Peacekeeper Gammak Base, murdered an entire Nebari battalion, even laid waste to a Shadow Depository. The guy was a devil: he raped and pillaged, he popped eyeballs— Crichton: Whoa-whoa! Where do they get these stories? Let's set the facts straight. First off, there was no raping, very little pillaging, and Frau Blucher popped all the eyeballs.
And again in "Scratch and Sniff":
Raxil: Two guns? I mean... I thought you were the Great Crichton & D'Argo! I mean... you blew up a shadow depository! I thought you'd bring pelshfer charges! And a plasma bomb! And a really big gunship! BUT NO! YOU BRING NOTHING! YOU BRING TWO LITTLE WEAPONS THAT WOULDN'T KILL A NIKNIK! D'Argo:(hesitantly) You... have heard of us? Raxil: Yeah. I've heard stories. But obviously they aren't worth a bucket of dren!
By the end of the series, Stargate SG-1 has made the entirety of Earth's forces both famed and feared throughout the Milky Way Galaxy.
A few specific examples:
In "The Warrior", a newly-introduced Jaffa greets SG-1 with "I honor he who would kill his god. And to his brethren of the Tau'ri: slayers of Ra, Hathor, Setesh, Heru'ur, Sokar, Cronus, and Apophis."
The Goa'uld Nerus arranges to end up at Stargate Command under the pretense of helping them defeat the Ori (he's actually The Mole.) His introductory scene finds him extremely disappointed at the personnel changes in SG-1 as he was really looking forward to meeting O'Neill and Colonel Carter.
When SG 1 gets captured in "Off the Grid", the bad guy (a small-time player in the Lucian Alliance) knows exactly who they are.
Same thing happens in Stargate Atlantis. Word spreads pretty quickly around the Pegasus Galaxy about the people living in Atlantis and battling the Wraith (and later, the Replicators.)
Suits has a subversion. An opposing lawyer fully expects Harvey to know him by reputation even though he usually practices in another city. However, Harvey never actually heard of him. Turns out the guy is so good that none of Harvey's lawyer friends and colleagues are willing to talk about the brutal trouncing he gave them in the courtroom.
In Highlander: The Series, Duncan MacLeod is a legend in his home village of Glen Finnan. "He came back from the grave, took up his father's sword and slew the Viking". Duncan has to do it all over again, though, because when he killed Kanwulf the first time, he was a newborn immortal and didn't know he had to take his opponent's head.
Naturally, there are a ton of stories floating around about Methos, which enables the fake Methos in "The Messenger" to do his thing.
By season 11 of Red vs. Blue, the Blood Gulch Crew's exploits have become well-known enough for a band of rebels to look up to them for inspiration and leadership.
"When can their glory fade? O the wild charge they made!"
In BattleTech Aleksandr Kerensky is well revered by everyone in the Inner Sphere, and the Clans view him as a Messianic Archetype. Jerome Blake is also revered as this by ComStar and the Word of Blake.
Go, ye heroes, go to glory — Though ye die in combat gory, Ye shall live in song and story!
In Dead Rising 3, stand-outs of Frank West and Chuck Greene from the previous games can be seen in Los Perdido's museum exhibit on the history of zombies.
This is one of the defining features of Dragon Age II. Since it takes place over several years, your exploits are talked about quite frequently.
This is true of Mario in most incarnations where he can talk to people, but especially so in the RPGs.
Averted in Brütal Legend. In the end, protagonist Eddie Riggs doesn't get fame, glory or even credit for the things he did. He wouldn't have it any other way.
He's a roadie. That's kind of his job.
If Shepard had chosen to save the council in Mass Effect, there will be an advertisement for a movie of his/her heroics in the Battle of the Citadel in the sequel.
Though this is also subverted, as some of Shepard's greatest achievements, namely his/her victory over the Collectors and Reapers in Mass Effect 2is unknown to everyone, though Shepard is still well known and respected/feared by everyone anyway, as they are still acknowledged as a humongously huge Bad Ass.
By the time Mass Effect 3 comes around, Shepard's reputation is so great that his/her commanding officers willingly stand aside and allow him/her to make the decisions in the greatest war humanity has ever been involved in. They outright state that Shepard is the only hope the galaxy has.
In Assassin's Creed II, bards will sing about your exploits to you, and if you are notorious, wanted posters with your name and (obscured) face start appearing, while town yellers will start denouncing you. During multiplayer, you can sometimes hear the town yellers mentioning your single-player character.
During the last Lair of Romulus in Assassin's Creed: Brotherhood (Basilica di San Pietro), while you're trailing the target cardinal, a group of other cardinals can be overheard discussing you:
Cardinal #1: His name is Ezio Auditore.
Cardinal #2: Who?
Cardinal #1: The Assassin. Killed the Banker. They say he walks the halls of il Vaticano ("the Vatican"), with no one able to stop him.
By 1524, legends about Ezio's skills have spread as far as China.
Especially the Vortigaunts, who consider Gordon Freeman to be their own personal Moses and call him "the Free Man."
Master Chief Petty Officer John-117 is this in Halo. Many of his fellow soldiers are well aware of his abilities, senior officers are willing to take risks based on his assessment, and he does get remembered as the saviour of humanity in the ads leading up to Halo 3. Even the Covenant are also aware of him, as "the demon" that destroyed one of their holy relics.
In Halo4, this gets bumped up even more: the Master Chief is a freaking legend, to the point that a superior officer who disagrees with him and orders his arrest for disobeying a direct order and committing an act of mutiny and desertion, all legally justified, is later removed by Command. Plus everyone in the Infinity choose to help Master Chief then follow the captains orders.
Metroid. Many characters know of Samus Aran's exploits. In Prime 3, many Federation soldiers are starstruck when you talk to them. And that's not even getting into the Space Pirates' immense fear of her.
In the Mega Man Zero series, Zero is well-known as a Maverick Hunter even a hundred years after he went missing, and the reactions of who he meets differ depend on which side of the war they're on, with the Resistance and Ciel viewing him as their resurrected savior, and Neo Arcadia viewing him as a Fallen Hero who now works for terrorists.
Fallout: New Vegas: Get enough status with the NCR, and they'll laud your awesomeness whenever you show up. Many other factions do the same. Quite a few other people recognize your sheer badassery; after freeing Raoul (requiring you to cut a swath through a dozen supermutants) he says "When a supermutant tells you to do something, you do it. Well, maybe you don't..."
In Monster Racers, as you progress through the tournaments and the various areas, your player character slowly becomes famous. Many of the generic Non Player Characters you meet in later levels already recognize you, and many are excited to race against you. Eventually, the two snooty fangirls for Santos and Reinhart even switch over to becoming fans of you, and act as if they were really rooting for you all along.
Garret of Thief doesn't often get recognized on sight (he's a thief after all, if he's doing his job properly, people won't know what he looks like), but his name certainly becomes more and more well known as the series goes on. By the second game, he's on the City Watch's most wanted list, and by the third he is Shrouded in Myth and considered able to steal just about anything, from anyone.
You get more and more famous as you progress through any The Elder Scrolls game. You get songs written about you and everything.
In the early acts of Titan Quest, various storytellers and poets will tell you stories from Greek, Egyptian and Chinese mythology. By the time you get to Act V, they're telling stories about you.
A codec conversation with Kevin in Metal Gear Rising: Revengeance R04 reveals that Sundowner used to have quite the reputation in his pre-cyborg soldier days.
In Dawn Of The Dragons, by the time of the sixth quest zone (which takes place several months from the beginning), people start talking about the dragon-rider as if he/she is a hero on par with the mythic figures from the age of legends. By the ninth quest zone, the dragons are referring to him/her with curses and have made killing the dragon-rider their top priority. The dragon-rider can't escape this trope even after being teleported to the other side of the continent. He/she almost immediately becomes The Chosen One destined to free a Slave Race.
According to canon, Ryo became the champion of the first official King of Fighters tournament by defeating Geese. Which took place over a decade before Geese's fated match with Terry. Because of his prowess, he has earned the title "Mouteki no Ryu" ("The Invincible Dragon") and has gone on to become legend.
Robert is credited for defeating Mr. Big, who's known to be one of the most feared and powerful crimelords in South Town, to help save Ryo's sister, Yuri. In addition, he's recognized as Ryo's equal in prowess and stature and is famed as the first known foreign practictioner of Kyokugenryu Karate, and as the first foreigner to ever master the discipline. Robert has also been acknowledged as a "natural genius" by friend and foe alike, which has earned him the title of "Saikyo no Tora" - "The Mightiest Tiger".
In El Goonish Shive, Tedd appears to be this. At least amongst the magical community; Jerry could identify him just from Susan's brief explanation. Jerry claims it's because of Mr. Verres, but only after a significant pause.
Also Justin, after the Fire Summon and Taurcanis Draco attacks.
This is invoked by Open Blue. Adding "Extra Information", rumors surrounding your character, is part of the character profile template.
The Outcasts of Tasakeru will be "whispered of as legends" in the future, up to 150 years or more after the events of the story.
Over the course of Worm, the Undersiders and Travelers become national news for having taken over Brockton Bay.
Avatar: The Last Airbender : Many of the characters are famous in-universe. Aang, as the avatar, is the most obvious. His fame is a mixed blessing; people either greatly respect him or want to kill him. All members of the Fire Nation royalty are famous: Zuko for being the disgraced prince, and Iroh for being The Dragon of the West.
Danny Phantom, of said show, becomes famous. His powers become well-known in the Ghost Zone, and despite initial skepticism, in the human world as well. Earlier in the show he is more infamous, believed to be evil, although by the end of the show he is hailed as a defender of the world.
Ben Tennyson's identity as a superhero is revealed in the first episode of Ben 10: Ultimate Alien by an investigating fanboy and he has mixed feelings about it: on the one hand, he's the idol of millions of young people and kids, but on the other hand he's hounded by a TV pundit who tries to convince everyone he's a threat (even though the guy's pretty ineffectual and has to resort to a Killer Robot like most of Ben's foes). Eventually the adoration wears thin as he can't even enjoy a smoothie break with his team without being mobbed by fans, and the strain it puts on his relationship with his girlfriend.