This is taken and expanded upon from my post here (that covers other "fix" areas): community.wizards.com/go/thread/view/758...
Balance each class Equally across all pillars! Since in general consensus the fighter comes up the most often i'll use the Ftr as an example: yes we know fighters can fight - check we have combat down, but they can also lead; countless examples are in history and stories, myths and legends - bam - social pillar. Fighters have also been known to lead troops on campaigns exploring as well as sometimes conquering the 4 corners of the earth - exploration.
Now expanding upon this for the CORE FOUR (Mage, Fighter, Cleric, Rogue):
Mage (pretty much already done for us):
Combat: spells like fireball, lightning bolt, etc.
Social: spells like Charm Person, Mass Suggestion, Pretidigitaion, Etc.
Exploration: Spells/Abilities like Scry, Legend Lore, Phantom Steed, Teleport, Etc.
Although Some of these could be the domain of the Bard...
Combat: some skill with weapons and armor as well as spells like flamestrike and spiritual weapon/hammer
Social: spells like command, or just a priest on the pulpit
Exploration: spells like detect this or that, divinations, oracles, weal or woe
Combat: tricks that use the rogue's opponents weaknesses to the rogue's advantage. Disney's Aladdin escaping the town guard in the opening scene
Social: Bilbo Baggins sweet talking Smaug the red dragon
Exploration: finding and disarming traps, escaping a dungeon/sewers (think Mouse in LadyHawke)
Feel free to help me expand upon this!
Really feel free lol :P