Hi, thought I'd throw some ideas at you - maybe some will stick:
1. The Priest - the idea of a crucified Legionnaire becoming a holy man is actually pretty awesome. I think he should have two custom weapons - a sword (claymore if possible) called Brimstone; and a gun (probably a magnum or desert eagle) called FIre. He should probably be rabidly anti-Legion - becoming unavailable as a companion if the player is aligned with them. If the player's karma is really low, the priest should try and get the player back on the "right" track.
I do have an alternate, or additional section to the back story idea (I apologize for the cliches) - the Priest was an old man in Searchlight when the Legion released the toxic canisters and killed or mutated everyone in the city. For some inexplicable reason, the Priest doesn't die, but instead becomes younger, stronger, faster, and smarter - which he takes as a sign from God. Radiation doesn't appear to hurt him and he can shrug off most damage that would kill lesser men. After the attack, he witnesses Legionnaires running away from the firehouse, and filled with a righteous wrath, kills them. He decides to go on a crusade against the Legion, going on raids into their territory before eventually returning to the Searchlight Church. He can be found reading a bible. The ghoulified NCR troops ignore him for some reason; while the Legion call him the Avenging Angel and try to stay out of his way - his legend growing every time he appears to die, only to stand back up completely healed. Whether or not his superhuman abilities are due to him being some sort of mutant or divinely gifted should be left ambiguous.
It's a shame Joshua Graham couldn't be like this - would have made Honest Hearts so much better.
2. The Nun - this is not a criticism per se, but the ideas I've heard for this character maker her sound awfully close to Rose of Sharon Cassidy. Other than the "Two Mules For Sister Sara" idea mentioned before, I got nothing worth mentioning. The con woman could have a criminal gang hunting her because she stole something valuable from them (a diamond, secret plans, the boss's pet kitty, etc.). Would be cool to have her trick the Courier into doing some jobs for her with the end of her quest line leaving the Courier in a mexican standoff - The Good, the Bad, and the Ugly-style. Depending on the player's choices, she can either leave the player to their fate and vanish once and for all, or return to help.