My favorite companion from any of the Zelda games would definitely be the King of Red Lions. Unlike Fi or Navi, he is not capable of following you around at all times, and thus is significantly less annoying. He is usually quite helpful throughout the game, going useful tips and advice. Plus, I loved how he fit into the story when you are least expecting it.