I was thinking about this and it would be interesting if the skill in which you gain % when you gain a level would be a skill you have used during that level. (chosen randomly among all those you used, with also a few you didn't use in the equation)

I think it would be more interesting than it being completly random, and it could also help classes like invoker or assassins who needs certain skills at maximum to learn others.

Just my 0.02$

It makes a certain amount of sense, but I can't help but picture a thousand lowbie mages demanding each level to tank for one round so they try to parry at least once.

I'd rather drive, choke, cutoff, and other skills of that nature go up because you just don't use them much while you rank but they are still useful. The ones you do use will go up, just slower than you'd prefer sometimes.