Well the choices given make it a easy choice for me and it always is in my view -- Link and Midna.
You have this unlikely partnership, you have Link, a humble village boy, who has this noble aura, he is generally seen as a role model among his peers. Then you have Midna, a Princess of a darkish tribe, who has a, let's say, odd persona. The two are brought together by one common goal, defeating Zant, but generally for different reasons. Midna, during the beginning phases, uses Link to get what she wants -- Link just wants to save his friends as well and is dragged into a bigger scenario.
As the two carry on the journey you see their friendship change and advance, their different motives become one after a while. Link realises the bigger picture and that it's not just about saving his friends, but instead the "whole" of Hyrule. While Midna comes to the realisation that it's not just about her getting her powers back, but instead it's about putting aside past complications between the two worlds and instead about saving Hyrule.
Link and Midna grow to care for each other and more importantly they grew into the most unique and strongest duo to date.