On the topic of cookie-cutter characters and tweaks, here's something I've used to decent effect. Every player that gives you a backstory gets "freebies" for his/her character based on said backstory. Go with what works for you, but I generally hand out 2-3 "skill steps"... basic skills get trained, advanced skills become basic skills for that character. I've substituted logical equipment in place of a skill step if something strikes me (sometimes even giving Good or Best Quality stuff, making it clear that these items are dear to the character and should not be parted with).
For example, in my current game, I have a voidborn Tech-Priest who grew up on a station orbiting a cometary body in the outskirts of the Calixis sector. Several other Tech-Priests around (it was a Tech-fiefdom, in fact), but they primarily studied orbital mechanics. So, not being interested in that, he studied with the station Biologis. Result? He gets Medicae as a basic skill for free. Also, his mother (another Tech-Priest) was killed during a raider attack. He asked if, in lieu of anything else, he could have a servo-skull. Sure, no problem, one servo skull with nothing in it, because it makes sense for a Tech-Priest to have one and he gave me a good reason.
Another example, same game. I have a Metallican Gunslinger Scum whose backstory is basically that he was a member of a minor noble house that was taken out by a rival house... but said rival house used warp sorcery to do it. He, not knowing that, swore vengeance, and broke into their manor to get evidence to take to the planetary enforcers, and wound up coming across cult paraphernalia. He took that to the Arbites, and the Arbites stormed the manor and executed the nobles they could find. So I gave him a best quality autopistol in place of his regular one, Forbidden Lore - Cults as a basic skill... and a watered-down version of the Noble homeworld drawback from the Inquisitor's Handbook (he didn't take that homework because he said he wasn't a noble anymore because his entire house had been destroyed).
So yeah, it's the little things that can really set starter characters apart. And they don't have to be incredibly overwhelming. (GM Tip: They don't even have to come up much! Sometimes just having something on the sheet is enough for a player to feel like his character is different from the other six trillion guardsmen out there).
Speaking of the Scum... the income system in this game is messed up, especially for the non-Noble Scum out there. There are horror stories about Scum being unable to afford ammo for their guns, let alone have any kind of bribe money to get information out of anybody. I recommend normalizing income across careers quickly, or at least giving them some kind of stipend. It may be a meta-game dynamic, but nothing sucks quite like being out of bullets and unable to afford more while the Tech-Priest sits on several hundred thrones, but won't help out any because he's scrimping and saving for his mechadendrites.