??? In my suggestion, the "relevant" stat for the skill (Dex for Acrobatics, Str for Athletics) determines whether or not you can train it as an "extra" skill. In other words, if you have a 16 Dex, you can train one extra Dex-based skill.
I admit this would lead to skill bloat and reduction in the value of skill training feats, but the OP didn't seem to be too concerned about that. But I think it would be pretty evenly fair to all classes, since almost everyone would have a 16 in some stat.