Cherche and Lon'qu where my two choices, if only because of how interestingly extreme Cherche was and how she, among all other women, seemed to hit closest to home to softening up Lon'qu. Lon'qu in general seems to fit the whole strong silent type with a dark past which was cool.
Personally though this was a tough choice, I'm a huge fan of Panne (Doesn't put up with any BS), but as I played through the game Cherche became a quick favorite.