Sounds like, if you want to follow the original plan, at least, what you want to do is make them all situational, then. That obviously runs contrary to simplifying things, but if you can create a certain set of relatively equal distinctions, you can let people specialize without going all crazy or making it a pain to track.
For instance, supposing every enemy (and possibly other players?) had a race and elemental affinity. Someone's skills could look like:
+3 Attack
+2 vs Demons
+1 vs Undead
+3 Defense
+1 vs Ice
+2 vs Dark
Varied, but still following a basic framework, albeit a lot less interesting than a chance of extra fire damage or whatever. Generally no less interesting than a straight attack or damage bonus, though.
The only real trouble, of course, is that everything has to be roughly equal in use to be a good option. You probably wouldn't want a distinction with only two or three choices anyway, but gender would be an obvious bad idea, for instance, because almost all enemies appear to be either male or genderless. Assigning everything an element in roughly equal proportions could also be tricky, which might lead to Dark attack or Fire defense being the most often-used skills, for instance.
And of course, this sort of framework doesn't necessarily preclude everything else, but it's a good starting point and obvious pool of default options.