They say everyone gets 15 minutes of fame in their life, doing something special that gets them noticed. With television and internet, that fame can be longer than 15, and sometimes more often than once. Just look at reality tv, especially Amercian Idol type singing shows. People go crazy for these things and as it is tryouts, you can see all sorts of weirdness than the previous gameshows.
However, what about in the fictional world your game takes place in? Do people have their own way to acknowledge those who are famous for something or other. Bards singing songs, museums having galas of famous artists, top ten lists in magazines, popular videos in Youtube and so forth.
I can think of many times in video games or shows where a character was given fame for something they did and now part of it is dealing with the consequences. Sometimes, the fame is unwanted like on Blade 3 where Blade was all over the news. Just imagine how a criminal in a Shadowrun game would deal with a city wide manhunt with Matrix alerts, giant video screen billboards and so forth. Even open world games like Infamous or Watch Dogs has it where people will take your picture or cheer for you as you go by if your in game popularity meter is in the good. Maybe your villagers thank you or run from you, maybe they just don’t care.
Also, sometimes being famous is not quite what you wanted it to be, for whatever reason. Mickey Mouse was gladly talking about how he took out seven in one blow. Little did he know people thought he was talking about giants. Now he is the Giant Slayer that is out to save the city. So, maybe your heroes are dragon slayers, having bested a dragon terrorising the county. Now other dragons may want revenge, other beasts want bragging rights for taking out the dragon slayer, and so forth.
You can give rewards to the players for their fame. A sponsor, free meals or little trinkets and services are all things that don’t overly push the power levels in a direction that they cannot support. The flip side is they need to do things to pay for this, such as opening a new building, taking part in a court ceremony, putting on a charity concert, the list of options is almost endless. Just look at what real world people go through, how many people spend time doing convention after convention because it pays the bills. PCs usually won’t have that issue with the plot keeping them busy, and usually in the money.
Fame is fleeting as well, unless you keep yourself in the public eye. So many celebrities keep making appearances and things to remind us they are out and about. Your characters don’t have that luxury if they are doing an adventure as well, so they will probably not last long in the public opinions. They cannot ride their fame forever, but they can definately milk it for a while. A smart player may come up with ways to maximize their fame, and let them so long as it doesn’t unbalance the game in a way you can’t fix. If it starts to become a problem, try to deal with it in game or out, as everyone needs to have fun.