Okay, then you don't want to run a heroic game. Seems a bit odd to me, since I think that's precisely what Conan is about.
Heroes like Conan, Achilles (nice example), maybe Leonidas etc. set the benchmark at level 20. Level 20 is about 4 times as powerful as level 10. So there's a lot of margin between those. Even 2 or 3 levels can mean a world of difference.
NPC advancement belongs to a different thread, but as a rule of thumb I've assumed something like 1000xp per year after adolescence, leveling out at some point. Level 10 maximum sounds about right for normal, unimportant NPCs. No limit for the important ones, which would advance much faster.
So in short, I'd set the threshold for "well known hero of world-wide renown" at around level 16.
In our game, we've conquered cities, retrieved ancient relics, slain a Demon, disposed of a Frost Giant, discovered an Acheronian colony, vanquished a Wyrm, and had a dance with the Thunderbirds, to name a few. Still our heroes are not widely known and that's okay -- news don't travel fast in a medieval world, whereas we get around quite a bit. But I'd feel rather shafted if we were still goofing around at level 7 trying to recover the farmer's stolen fertilizer.