I almost think that the base skill resolution should be tiered
Untrained: Raw Ability check
Proficient: Ability check with proficiency
Expert: Ability check with proficiency and reroll or double proficiency (your choice)
Master: Ability check with proficiency and reroll, double proficiency, or minimum of 10 as roll (your choice)
Grandmaster: Ability check with proficiency and reroll, double proficiency, or minimum of 10 as roll (your choice or 2)
Skill Feats require Expert or Master or Grandmaster
It seems to me that there are four axes we can use for this, as noted in part by
@MuhVerisimilitude. I'll be using terms I'm inventing more or less on the spot, other than "impact" since that's already been named, but hopefully they will be reasonable.
You have two of those four elements. Quantity, which is all the bonuses (proficiency), and control, which is all the manipulate-the-die stuff (reroll/advantage, minimum roll result.) The third, as MV says, is impact, which is the potential
effect of the result. Finally, as noted upthread, we have access, where gaining greater skill opens pathways that were not open before. Each has good and bad:
- Quantity is good, because it clearly shows progression: numbers go up. It also innately carries some amount of "unlocking" things, in that when quantity is a valid way to grow, there can be target numbers that were once impossible and aren't anymore. Quantity goes bad when it gets out of hand, whether because of too much bonus or too many bonuses. Further, just because something becomes theoretically possible does not make it practical; all of these axes are affected by this to some extent, but quantity is the most susceptible.
- Control is good, because it keeps things grounded. Both targets and bonuses remain familiar, and if someone says they passed a DC 30 check, you always know that that is supposed to be a rough thing--interoperability. Control goes bad firstly when it deadens choice and distinctiveness (e.g. the way Ad/Dis is massively over-used in 5e), but more importantly, when it fails to actually show growth. If the boundaries never expand, if the things you can do never actually change, you just are less likely to screw it up...the growth can feel muted at best and nonexistent at worst.
- Impact is good, because it directly shows how things get better. You don't just nebulously succeed 5% more often--you actually get more bang for your buck (sometimes literally more bang!) Further, by giving more impact, the stakes are raised; failure now carries the opportunity cost of not getting the extra things you'd get from succeeding. Impact goes bad in the qualitative version of how quantity goes bad: an ever-expanding horizon of what you can achieve becomes unwieldy and hard to grok. Further, oftentimes there's only so much you can do to expand impact, because it's deeply intertwined with the underlying design of the game.
- Access is good, because it walks a middle road between quantity and impact (what one might call "quality.") That is, you objectively gain access to something new, so growth is obvious and concrete, but whether and how you use that new thing depends on context and situation, reaping the best of both worlds. It also tends to be easier to design around, since it doesn't risk the ever-expanding issue for either of those. Access goes bad in the most obvious way of the four, the dreaded, "everything not permitted is forbidden." Further, while it is easier to design challenges around access levels, the fact that these things mix qualitative and quantitative makes it much harder to design the choices themselves, because they must be both mechanically useful and thematically warranted.
I think any system attempting to deliver a satisfying skill experience should aim to use all four approaches in order to balance out their faults. So, for example:
Someone can be Untrained, but still get various bonuses (e.g. Jack of All Trades.) They will always have the lowest tier of access (unless some other feature applies to grant it narrowly), but might have contextual sources of quantity or control. Impact is generally not available.
Moving on to Trained, this nets you a baseline of quantity (e.g. Proficiency in 5e) and most, but not all, access benefits. There may still be things restricted to higher development, but they're rare, and justifiably inaccessible to most. Control and impact are generally derived from context, not from how much one has learned.
An Expert gains reliable control features (e.g. 5e Rogue's Reliable Talent), and possibly expands their existing quantity features (e.g. double Proficiency in 5e.) All or very nearly all forms of access are now granted, some of which may (likely
should) give influence over impact.
A Master has the highest possible level of investment, and thus if it
can be achieved through this skill, the Master is capable of it, though dice may of course still produce failure. All four axes are at their peak, barring unfavorable circumstances, and conversely, favorable circumstances allow the Master to achieve things which some would consider impossible (or at least implausible.)
Coupled with the above, you need skills that are potent and flexible, and it needs to be clear to those running the game that that is what skills are for. To design or run skills as narrow, ineffective things that pale in comparison to other approaches is to basically make skills a superfluous element. Skills need to be genuinely worth using if people are going to want to use them!