I think if you have enough fame people should sometimes applaud, possibly have songs in taverns about your exploits. I'd prefer this to having people give you items. Obviously don't have them applauding everytime but if you have completed a heroic quest and word of your deed has met a settlement then I think something like that would be appropriate.
I like the idea of a name generator and random NPCs honestly. Everything is a tradeoff... abandon the realism of each of them having a set schedule and place to sleep for a more realistic number of people in the population. I'm in favor of that.
As for people reacting effusively toward you... there is another game but I won't mention the name because I'm not sure that's allowed, that even focused more exclusively on the way people react to you, and after having played that game I'm convinced there is just no way to do this in a balanced way that would not make you overly the center of the universe. It's very unlikely to not make such a thing also be annoying, especially if you are a hero, but also a covert agent type in your gameplay, sneaking for the greater good etc...
As for there just being enough people in the scene... I am worried about this myself. There never are enough people in these games... always so many more monsters than people in combat-based fantasy worlds, always imbalanced. I know the engine they are making is going to be superior to the one used in Oblivion... but just something to consider, With a PC 6 years newer than what was available at OB's release, even with OB's old engine, I can have all settings modified to maximum, high-res textures, VWD, UL, Better Cities, you name it in my OB build, and everything runs sooth as butter in almost any circumstance, but the only time a strain on the FPS occurs that really ruins the game is when there are too many humanoid NPCs walking around nearby. NPCs more than anything kill performance. I'm dubious as to how many NPCs can stably render even with the new engine.