I was thinking something like this:
Make the attributes* (Str, Dex, Int etc.) climb slower and be more like in D&D, where they affect more stuff and even a slight increase matters. Have every level for Melee, Ranged and 2 Magic skill (or whatever you call them) actually just give you access to more feats for that skill tree (and it would have more feats then previous games, especially passive ones) and you'd have to chose one from all the ones available so far each lvl-up, and have your attributes only increase every like 10 levels (and once for the first level in that tree) for each skill tree by the appropriate attributes (e.g. melee = +5 Str, +1 Dex, +4 Con; ranged = +3 Str, +5 Dex, +2 Con). And the two magic skills would affect Con (life basically) and the 2 magic attributes (Int and Wis - which fit Combat and Nature Magic respectively pretty well, don't they, and you can ).
*note that i'm using the D&D 3.5 type system and terminology to make it easier to understand
But anything that makes it feel less like just swinging your sword over and over and gives you more options (especially for the melee character) would be welcomed.