First off, folks, you need to widen your definition of 'hero'. A hero is not someone who does the greatest of deeds, or is the mightiest. A hero is simply someone other people look up to for whatever their reason.
However, hero and 'legendary' are not the proper terms to be using here. What Zanzi is proposing is not based on being a hero, nor a legend. It is based on sticking with this game, despite the bumps and tumbles. It is based on seniority. I suggest something a little different.
Before anyone comments on that, let me explain. In most places you work, the longer you have been there, the more benefits you get. It does not matter if you are the floorsweep, or the big guy in the big leather chair. Every year, they can get a pay raise, extra vacation time, seniority bonuses, or many other things. The point is, you get rewarded for loyalty, and time spent. Does the humble floorsweep get the same rewards as the chairman? Not in the least. But, he does get something.
In MB to CB terms, this is the Ring of the Past. For the people who have stuck around for the two years since then, there has been nothing but watching newbies become as powerful as you (for the fighters), or being called a n00b yourself by the folks who have been around a week just because your character is not maxed out. This has happened to many of us, including me. My very first character was laughed at and killed by a person who had been playing for maybe a week (you may remember how that turned out

). I had never trained, nor quested with this character. Would the outcome of the fight changed any if there was some way of seeing that "This character has been around for some time". No, not likely. But the mood would have.
Now, I have seen the arguments against this, and I dismiss them. Should players be rewarded for staying around? Yes. Does it have to be 100% in character? It can, but does not have to be. That argument is silly. GMs can hand out money, PP, and items for being in events, as they should. Now, where do these moneys, PP (especially PP), and items magically come from? Why, that would be the GMs OOC pockets.
Now we come to rewards. All players are not equal, so all rewards should not be equal. The player who spent a week powerleveling two years ago, then comes back now should not get the same reward as the character who has spent a few hours a week in the game for the same two years. A player who did nothing but chat should not get the same reward as the one who did every quest they could get their hands on. A character that has never left the tavern in two years should not get the same rewards as the character that has seen every nook and cranny there is to be seen. This, folks, is how you make it in character. The following is a list of -could be- rewards.
The weekend warrior from two years ago: Special shiny polish for all their armor. What does it do? Not much, just helps you stand out in a crowd.
The steady-as-you-go leveler of two years playing (non-quester): Nifty weapons and armor no one else can get. What do they do? A bit of stat boost here and there, but nothing great. Oh, and they also get the shiny polish.

Bah, this is too hard listing off things that way. Here it is laid out. You can get MULTIPLE rewards for being in each of these categories.
High level (anything): Nothing. You can get a high level in a week. The high level is its own reward.
One year (this means your character has existed for one year, not that you played it the entire time): Shiny polish for all your metal tools. Special clothing that looks just a little different then everyone else’s. NPCs may give you better prices. Note that you do not automatically get these things, they just become available. IC reason: NPC says "You have been around for a year now (ignoring the ridiculous timescale we have now), haven't ye? You must be getting bored with your old things. Say! I have just the things. Right this way."
Two years: Extra shiny polish, and clothing that stands out in a crowd. NPCs give you good deals. IC: Same as above.
Three years: Same polish and clothing, but you have access to items that no one else does. Not sure what kind of items, but nothing that drastically changes your stats. Perhaps training and item costs would go down a bit more.
High hours: Nothing in itself. You can log in for a week straight and do nothing and get high hours. High hours is a bonus added to the times above. What do you get? Not really sure, as the game does not have a lot to offer yet. IC reason: NPC says, "I have seen you around quit a bit, haven't I? Come on in and I'll fix you up with something special." Player IC reason: You have been around the block a few times, so know where to find the 'good' stuff. High hours may change what you get from quests or as loot as well.
Note 1: You have to be doing -something- for hours to count, be it talking, moving, or anything else. Idle time will not count.
Note 2: To prevent old players who spent little time playing a year ago from coming back and 'Power-Houring', ONLY hours spent in the game over six months ago fully count. Perhaps so many hours per week would count after the six months. Let's say ten hours a week. Anything more than that would not be counted until they are six months old. If you stop playing for a few months, hours would be subtracted, as people (and NPCs) would start to forget you. Such is life.
Note 3: Hours are progressive. The more time you spend, the better the reward.
Note 4: You do not get a -lot- of rewards. They are more like milestones. After (x) many hours and <# year in game>, <this item> becomes available. You still have to find and procure it, though.
High level (fighter-skill): This is what most of you see as heroes. Once you have a year under your belt, and have a high level fighter, you can get rare weapons in the skill you are high in. The higher the level you are, the nicer weapon (or armor/shields for those skills) you can get. At two and three years, these weapons get even more unique. Not uber-powerful, just unique. Perhaps some of them will never break. IC reason: NPC says: "You have spent a long time training with me, and I think you are ready to have this."
High level (crafter): Cooking, mining, basket-weaving, whatever. These folks are known as heroes to others as well, even though they may have never done great deeds. After a year and a higher level, you get better tools of your trade that allow you to do those trades faster or better. You may also get 'master' status in the crafts you are high in, and get special outfits to match. IC reason: NPC says, "<same as fighting>". Reason for master rank: It is a time thing, pure and simple. No one is given master status until they have been in the craft for a certain amount of time, no matter how skilled they are. This is taken straight out of real life. Now, for two or more years, you may get a 'Grand master' (or some such) status.
The Quester: Do a lot of quests, be around more than a year, get more quests. Simple. IC reason: NPCs are going to use a faction system that makes you known to them as you do more quests. At a year, some would say something to the affect of, "I hear you be quite the adventurer, and still alive to boot. You might be just the person I'm lookin' for, if you be interested."
The Explorer: What reward can you give to someone who has crossed the world hundreds of times, and seen all there is to see? No, not more to see (but maybe). Give them better shoes (or ointment for those without shoes). Seriously. The shoes would give them a bit of a speed/stamina boost. IC reason: Do you need one? They have been running all over the world. A bit of a speed/stamina boost is deserved. What, still need an IC reason? Fine

: NPC says: "Sonny, your feet look like they're about to fall right off. Give me a moment, and I'll give you something to open the world to you!"
The Talker: Ya, that would be me. We deserve a bit of a reward as well for staying around for a year, and never using a single feature. Not sure what, though.

Unless, perhaps, it is putting that character's name somewhere. *shrugs*
So, what does a character get who is a high level in a lot of things, is a good fighter, and has been playing for two years? Extra shiny armor that no new person can get, a cool swords handed to him by his trainer, sweet cooking pots for which to make excellent stew in (but not much better than everyone elses), unique clothing for which to do his little turn on the catwalk, and some interesting quests to go on. And every single bit of it -in character-.