Well, what's your solution?
I guess I didn't really answer this question...
There's not a perfect answer, but 4e does show how it can be approached. I'd say 4e probably does about as well as D&D ever will. First of all it insures that they have real combat equality, and that each class has a role which guarantees them a unique way to contribute. Beyond that the skill system is quite deep and central to 4e. Though the 4e fighter (inexplicably) got shorted a skill vs all the other classes skills are still central to the game and he's on an even footing there. Powers rarely trump skills, but more often enhance them. The whole system of doing crazy stuff with skills, page 42 etc, also means its an easy and often-used thing where the broad skills come into play in a big way. There are quite a few non-magical utility powers which are quite useful as well, often as useful as the utility spells. Wizards DO get rituals, which are quite powerful, but limited and costly. As the PCs ramp up to the high levels where magic gets more powerful the fighter also becomes sort of super-heroic, gains PP/ED stuff which can be pretty fantastic, and the DM can scale up what skills do to almost any degree as he/she sees fit.
This is NOT perfect. A clever wizard player in 4e can gain a LOT of flexibility (I ran one and really pushed it to see just how far I could go, not quite to AD&D levels, but I got some pretty amazing mileage out of it). At least the two are playing the same game now.
You could even it out by making magic overall a more limited thing. If say all magic was ritual magic and required special conditions, etc to work. Its quite possible to imagine a wizard for instance that did nothing but make charms, potions, curses, and whatnot, scryed, etc etc etc. Such a character would be a lot more limited, but even then they'd have access to some plot power that is missing from other PCs, that's just part and parcel of "can defy the laws of physics". I mean just being able to do the lowest level 4e rituals in the real world would probably be worth infinite wealth!
Perhaps, though you'd get a lot more traction on the Fighter chassis under such specialties as Pirate, Gladiator, Manhunter, and anything contained within the martial cousins. I think you also find a more meaningful path in the way of skills, story, and non-combat opportunities with them, too. A lot more. You'd be giving combat back to the Fighter in all its forms and allowing it to shine through any number of appealing and purposeful applications. Granted, you'd want more elaborate specialties to go with them to account for differences between types of Rangers, Paladins, Monks, and Warlords, and a number of unique expertise dice options with which to choose from, but if it were all contained in the Fighter, he'd be as robust as anything magical or skills-based. Through his diversity, he becomes more versatile, at least when speaking to the social and exploration pillars. I think, for Fighters, combat is already a shoe-in.
Yeah, I think I'd do it in 2 tiers. There'd be 'sub-archetypes', the barbarian, the ranger, the knight, the Warlord, and then there would be things that were more social/circumstantial like "Gladiator" or "manhunter". Admittedly some are grey areas, like "knight" that both imply specific fighting skills and a certain social and cultural origin. The point being many pirates could be fighters, but many might also be other classes. Its possible some knights might not be strictly fighters either, OTOH most of them probably would be to some extent. Maybe 'knight' could be 'warrior', a full-time professional fighter of whatever cultural type is appropriate, and say 'noble' could be a theme/background that would give you the feel of a knight when combined with warrior (IE you can now fight from horseback, get some appropriate skills, etc). IMHO a lot of this can be story anyway. Remember, OD&D had nothing but "fighting man", which was supposed to be ALL of these things. If you wanted to run around calling yourself a barbarian you were free to do so. That had a few weaknesses (not wearing armor was suicidal mainly) but clearly it could work fine with even some simple feats (IE the 'plot armor' feat that lets you be bare chested and just as well protected as a guy in plate armor).