I've also considered removing the notion of skills altogether and just counting all the other character selections to be proficiencies that you can add to a situation if it's justified. If you're Wizard, your class gives you proficiency when trying to discern arcane knowledge with an Intelligence check. If you have the Soldier background, you have proficiency on the Strength check to knock a guy over. If you know Elvish, you have proficiency in the Charisma check to hail the elven king. I think it could be a nice, rules-light alternative, but it's certainly a departure from the usual rules (so I'm a bit reticient to add it to my regular games).