Skill Training and Backgrounds help, but sometimes they really don't cut it. For the sake of argument, let's imagine an alternate universe where DnD kept its wargame roots.
You have two iconic classes: the Skirmisher and the Knight. The Skirmisher has always been mercenary in flavor, ever since the beginning; a tricky bastard who lives for combat and showing off his skill. The Knight, on the other hand, was flavored a wealthy landholder and a master strategist; calling advice to his allies, blocking and running interference, and especially meeting with enemy and allied commanders. In this alternate 4e, the Skirmisher gets a rather limited number of skills (Athletics, Intimidate, Streetwise, maybe Bluff or Perception) while the Knight got much more (Diplomacy, Bluff, Intimidate, Insight, Streetwise, History, Heal, Athletics, Endurance, etc.).
Suddenly, an alternate 4e player shouts, "Wait! My backstory says my Skirmisher was a cunning thief and master of stealth before joining the army! Why can't I have as many skills as the Knight to round out my concept?"
Well, why not?
My best advice would be to give the Fighter Athletics for free, give the Barbarian Endurance for free, and add Insight onto the Fighter's list. That at least keeps them equal with most of the other classes. Once that's done, think about taking a good look at other "one for free, choose three from the list below" classes, and think about bumping up their skill list. Make sure they've at least got one combat skill (Athletics, Acrobatics, Heal, Intimidate, Stealth), one knowledge skill (Arcana, Dungeoneering, History, Nature, Religion, Streetwise), and one social skill (Bluff, Diplomacy, Insight, Intimidate). But, preferably, give them two or more each for the sake of choice. Sprinkle Endurance, Perception and Thievery to taste.