This is an extremely rough idea and it would need to be worked out to be usable, and better names for the categories, but I thought I'd put it out there to see what people think and if it sparks any additional ideas.
Three categories of skills
General
Class
Untrained
General Max Ranks = Level
Class Max ranks = Level +3
Untrained Max Ranks = 1/2 Level round down Min 0
Then offer each class a mix of each based upon each class having some class, some general, some untrained.
Then you need to increase the skill points by +2 for each class.
Though you may not necessarily start the game with a bunch of 4s in a skill you could concentrate on a few to increase over time and get to the max ranks eventually. Or you could concentrate all your points one level in a single skill, and then maintain it with 1 point each level while concentrating on raising another to max ranks. It's a slower progression for skills overall, but it balances out as you reach higher levels.
Then a rogue who has Perception as a class skill could have a potentially higher score than a Fighter who has it listed as untrained.
You could then offer feats that increase the level of a skill by one. From Untrained to General or General to Class.
For multiclassing it takes a little math but to be honest a simple spreadsheet could be made to keep track of it and it's a lot easier than figuring out cross class skills was in 3.5.
Fighter 3/Mage 3
If the fighter has Spellcraft as an Untrained and Mage has it as Class skill...the max ranks are 6 from mage + 1 from Fighter so max of 7. Where as a 6th level mage would have max ranks of 9.
Remember this is a rough idea, and any input would be appreciated. I'll update the post with any changes if the idea takes off.