Typically, my friends and I just screwed around and latched onto the characters that appealed to us the most.
I found Nu/Lamba an interesting gameplay concept as she is a "glass cannon" type character, moreso in CS with the added rushdown (GOD I LOVE ACT PARSER!), Rachel is one of the most fleshed out fighting game characters ever IMHO and im currently anticipating Valky and Platina.
My friend likes hyper people and immediately picked up Tao as she was fairly accessible in CT and Tager just because he was buff and sounds like a god.
Another friend tried Caruru Crova, and liked the puppet's whole "1 hit = infinite" thing, and hakumen because C spam means win.
Its all about personal taste, unless of course your a tier whore or something.