Jimmy Hopkins, from Bully. I was expecting a blank everyman character going into this game, but Jimmy has a strong personality and background, and is a very believable character. He's rude, overconfident, shortsighted, and pretty thick at times--but he's still a sympathetic character due to the upbringing you know he's had and the fact that he always does the right thing in the end. Bully's full of great characters in general though; Jimmy just gets the most screentime.
Even just watching bits of Portal has made me fall in love with GLaDOS. I'm interested in that game just 'cause of her, since I don't like puzzle games as a rule.
Veronica, from Fallout: New Vegas is probably more endearing than anyone else I've encountered in a video game. NV was really good about characterizing companions. Her backstory is rich, and her quirky mannerisms are charming. Hard to really explain without just stating everything she says and does.
Samus Aran. The people who said that Samus had no characterization before Other M obviously never played Fusion, where there was considerable dialogue and narration by Samus, but where she wasn't a simpering, spineless weakling. If you remove Other M from canon, then Samus is a strong and compelling character and one of the best "non-bimbo female protagonist" icons in the medium.
