hmm.... that's a tough choice. Here's a few that come to mind:
Sonic and Tails, mostly Tails, but that's probably due to fox bias.
Sam and Max, particularly Max though they play off each other really well.
Fox McCloud from StarFox
Rif from Inherent the Earth. A neat little game, though some of the puzzles were a bit too simple.