In fact, the power curve and the rate of advancement don't mean anything without the other.The power curve is at least as important as the rate of advancement.
But power isn't one-dimensional either, and certain elements of the power curve strain credibility, while others seem perfectly natural. It doesn't seem odd at all for Robin Hood or Legolas to more-or-less always hit and more-or-less always kill his target. It doesn't seem odd at all for Musashi or Lancelot to do the same with his sword -- or even with a wooden sword.
It does seem odd that these characters know they cannot be killed, or even meaningfully hurt, by the first 10 arrows they take. We can certainly narrate our way around that, but it does feel "unrealistic" to many, many people.
Magic also feels unrealistic, of course, but there things get murky, because we all know magic isn't real -- but some kinds of magic nonetheless move the game away from "realistic" and toward "unrealistic", because they imply a world nothing like quasi-medieval Europe. With cheap and easy magic at their fingertips, spellcasters could presumably create an unrecognizable world. At the very least, certain spells, or combinations of spells, make armies obsolete or make standard adventures meaningless. On a larger scale, they would produce an entirely different society.