I originally posted this in the Cheat & Hints section a few days ago, so I'll repost it here with some perk ideas, since it seems like its natural home.
As for perks/upgrades, I'll have to think about that one a bit more.
Charon - Trace his past and discover who brainwashed him into obeying whoever holds his contract. Upon finding them, you would them have the option of reversing it, thus giving him his free will back, or leaving things as they are. Either way, he will be remain as a companion.
Unique perk ->
Shotgun Specialist You gain 15% bonus damage whenever using shotgun-based weapons, and 15% damage to ghouls.
Clover - The quest could investigate her past; where she came from, where she lived, her family etc before she was brainwashed. Perhaps a diary found in her quarters could be the trigger. This eventually leads to finding a long lost relative. The quest ends with her getting her free will back, and rediscovering who she used to be before her life at Paradise Falls.
Unique Perk ->
Brainwash by sneaking up on someone you get the option to turn them against your enemies (or pickpocket, as normal) and fight on your side.
Sergeant RL-3 - His log files give evidence of the secret pre-war military base where he was created. Upon finding it you discover that his creator had extra modifications used on subsequent models that were never used on RL3, as he was the prototype. Finding the base and the logs allows you to upgrade and modify RL3.
Unique Perk ->
Robotic Manipulator same as above....by sneaking up on a robot you get the option to turn it against your enemies and fight on your side.
Jericho - As a companion Jericho has rediscovered his love of killing and his old raider past. As a result, he wants you to help infiltrate an old raider clan that double crossed him and stole the proceeds from a raid on a nearby settlement. This outcast him from the group and lead to him starting a new life at Megaton. He wants your help in getting revenge and reclaiming the loot.
Unique Perk ->
Raider Fire Grenade With Jericho as a companion, you have access to a flame based frag grenade.
Fawkes - Still traumatised from his years confined to a cell in Vault 87, Fawkes wants to return there in order to destroy it forever.
Unique Perk ->
Mutant Mayhem +20 to Big Guns, and +15% damage to Super Mutants.
Butch - Butch opens up to you and confesses that his bullying and tough guy image is just a mask for a neglected and lonely childhood. He had never met knew his father but stumbles across evidence that may lead to his whereabouts.
Unique Perk ->
Coiffeur You have the ability to perform haircuts on NPCs for extra caps. (sorry, couldn't resist it :laugh:)
Star Paladin Cross - Whilst as a paladin in the Brotherhood, Cross retired from active duty as she was badly injured in a fight against Super Mutants. The Brotherhood had gained some intel to an imminent mutant attack on a small civilian settlement and Cross was in charge of the squadron tasked with defending it. Underestimating the potency of the mutant forces, the Brotherhood scout party were forced to retreat and the settlement was presumed to have been destroyed. The guilt of having failed has never left, and Cross wants to revisit the settlement to look for survivors.
Unique Perk -> TBA
Dogmeat - While speaking to one of the local doctors, you discover that Dogmeat is dying. In order to save him its necessary to find the pre-war sugical equipment that will allow him to be operated on.
Unique Perk ->
Dog Lover With Dogmeat as a companion, all dogs will fight on your side.