Midna was always a favorite character of mine, someone who was a major part of the story, but unlike Zelda, actually accompanied you along for the ride, allowing you to see just how good of a character she is. Fi could've been that too had she been less obnoxious in design and better handled.
Bayonetta would be one that could easily slip into a like just for how she looks, but I think there's quite abit more to her that makes her seem way more exciting. It's the confidence, the charisma, the style, it all works to make her incredibly fun.
I'll add another later...