Skills are no longer a measure of what you can do, but what you are very experienced at. They have completely removed the "Skill roll", everything is now an ability check. Skills are now just a situational bonus to ability checks if it happens to fall under your skill. A character no longer needs a skill to make any roll, the skill only helps him succeed more often.
To me this just feels like a Pot(ay)to - Pot(ah)to case.
Skills have not really changed (in concept, I mean, not mechanics) from 3ed to 5ed.
Before it would be said that Ability Scores gave a bonus to Skills, and now it is said to be the inverse; before it would be a "skill roll" with an added bonus from your Ability Score and now an "ability roll" with an added bonus from your Skill...
But look at it with a practical eye and it's the same: the same two things contributing to a single check to determine whether you're successful in a specific action.
1d20 + Ability Modifier + Your Skill Bonus
1d20 + Ability Modifier + Your Skill Dice
The only practical difference is a mere detail in the "using skills" mechanics; where before skills gave a fixed adjustment to your roll, now you roll an extra dice.
And before (3rd edition) just as now, you could use your Ability Score only to perform most actions that were skill-related (except in the case of skills that were trained-only). You could climb a wall making only a Str check if you didn't have any points in the Climb skill; you could use Diplomacy with a Cha check only, etc.
How you gain your skills, however, is something that has changed drastically in this new edition.
I'm not at all excited with the idea of characters having "this and that" skill chosen in character creation and that's about it.
I understand that with the dice roll mechanics they're trying to reduce the difference between a low-level skill check and a high-level one, just as they did with Attack Bonus (a fighter now progresses from +1 to +5 BAB, instead of the old +1 to +20).
Nonetheless, I would throw in something like that instead:
* You choose a number of skills at 1st level, and you gain, say, +2 or +4 when checking that skill (or, if you prefer to use the new terms, then you gain that bonus when checking an Ability Score to do what the skill suggests - it's really the same).
* At every X levels you gain another "skill allocation slot" (or whatever you like to call it). With that you can either gain that same bonus to check new skills, or you can increase your check with a skill you already purchased by another +2 or +4 or whatever.
AND, if unlike me you like the idea of throwing and extra dice instead of a fixed adjustment to the roll, this could easily be translated into something like that:
* When first you allocate a "slot" or "point" or "whatever" into a skill, you gain the +1d4 on its rolls. If then you allocate another slot in the future, you increase that dice to d6, d8, and so forth.
This would keep skill progression more independent, give players more choice, and in my humble opinion make character progression more fun.
It would be similar to the 3ed rules for skills, but more attuned to the game balace in numbers that I believe the developers are reaching out for with this new edition.
I really love the 3ed skill system. To me it's one of the best things that edition brought.
Not only spending your skill points gave characters a great level of customization and depth, but it also made skills a very important part of the game (perhaps just as much as combat). And not just a side-rule to be used on the eventual occasion.
I've played sessions where the use of skills were 90% of it, and they were incredibly fun.
This one time while DMing, I set up a ruined tower with no monsters whatsoever, but to get to the top and retrieve the piece the players were looking for, they had to make tons of skills rolls, including Climb, Rope Use, Search, Balance, and several others, even Knowledge (engineering) to study the safety of a particular point of the structure.
On other occasions there were "town-sessions" where the players did no real adventuring but stayed in a city, and using the many skills to interact with the citizens made it all quite fun as well.
All that said though (and what a wall o' text)... I dislike the OP's suggestion of making skill progression entirely independent from leveling.
I know it would feel more "realistic" but to me it just wouldn't feel like a D&D thing...
I will most surely use some house-rules on the line of what I've mentioned above, but I'd love to see some such skill system incorporated natively in the 5ed instead of the current "skill-gain" system, which to me seems overly-simplified.
Simplifying is good, but over-simplifying not so much if the price is taking out a fun part of the game.