What I don't understand is that you claim to have played SD3 dozen of times, and ask for advice as to which story is the best. You probably know better than any of us, I played a through SD3 only once, although I did the begining quite a couple of times, and saw how the story was altered. If I am not mistaken, you can have npr(6 3) = 6!/3! = 120 different parties, and thus 120 different stories. However, only the 1st char really affects the story significantly, and it affects like the first one or two hours of the game, then all stories converge to the same story when they reach Wendel. So just pick the main character that grants you the best story, and use your favourite characters as the other 2.
Pesonally, my favourite main character is Hawk, because of his ability to reduce the probability to have traps in chest is useful. You can also have him as a side character and switch to him to open chests, but then you don't get him at the start of the game, and have to switch manually every time.
I also loved Angela, she's sexy, immature and rebel, I like that
Charlie is way too much immature, though, basically she's a very little kid.