One interesting thing 4e did was show concrete progress. Not in skill DCs, of course, but in monster categories.
At PC level 4, an Ogre might be a Solo or an Elite.
At PC level 8, an Ogre might be a normal monster.
At PC level 12, an Ogre might be a Minion -- you're so awesome, you can drop an Ogre with a single hit.
That can be viewed as a "progress indicator" for PC prowess.
Sure, a level-appropriate Elite is always going to be a challenge -- but from the standpoint of the fiction, you don't need to see it as an Elite. Instead, you can see it as an Ogre, and you can see that in the fiction, the PCs make a lot of progress relative to Ogres.