Two areas where you can really cut complexity are feats and spells. Each feat and each spell is its own separate, tiny rule. Reducing the number of feats and spells, or cutting them entirely, will drastically reduce the amount of rules that you and your players have to keep track of.
Another way to reduce complexity is to reduce the number of experience levels that you use, variant rule sets, such as E6 cut out a lot of the fat of the game, since many groups do not have campaigns that operate in the upper levels anyway.
As to your suggestion re: skills, you may want to consider using the Good Attack Bonus, Average Attack Bonus and Poor Attack Bonus for skills that fall into your three categories of proficiency... It reduces extra rules even more by relying on a set of numbers that everybody will be somewhat familiar with anyway...