Link/Midna
This is one of the more popular pairings of Legend of Zelda: Twilight Princess (despite the popularity of Link/Zelda, of which I'm also a fan). This is at least partially due to its status as one of the better examples of interaction driving plot and character development in a video game, and having several poignant key moments.
Midna herself states that Link has influenced her character motivations, after Zelda sacrifices her power to save Midna's life. Although Zelda implied that Midna had been acting at least in part for Hyrule as well as for the Twilight Realm, up until that point Midna had outwardly shown apathy towards the fate of the Hylians, and even regret that Hyrule could not remain in shadow. Over the course of her time with Link, Midna not only comes to see him as an equal, she also becomes very fond of him, and he displays non-verbal concern for her.
The eventual parting between Link and Midna is saturated with a sense of "what if" — Midna and Link have become through their character evolution people who could see eachother [and whom the audience could view to an extent] as legitimate love interests, which is represented physically by the curse on Midna breaking and revealing her true form.
However, Midna's relationship with Link [and Zelda] and her character evolution also led her to believe that the Mirror of Twilight, the only means by which they could see eachother again, was too dangerous to leave either whole or even in pieces in Hyrule. She breaks it: a bittersweet ending to their friendship.
Zelda/Midna
Zelda and Midna's relationship is also viable and also undergoes an evolution, albeit less central to the game and partially offscreen. While Zelda and Midna are implied to have first met a little before Midna and Link, they do not appear to know eachother well despite having made some prejudgements.
What Zelda first thinks of Midna is unclear, but Midna appears to express the same doubt in Zelda's abilities as she initially does in Links — thinking maybe of the contrast in Zelda's "carefree" upbringing and her own, in reflected roles either side of the Mirror of Twilight. However, Midna resists Zelda's attempts to save her life using the Triforce of Wisdom, seeming to belie faith in Zelda's gifts from the goddesses, and that she feels Zelda more vital than herself in their quest to save both Hyrule and the Twilight Realm.
Similarly, Zelda acknowledges an evolution in her opinion of Midna when she remarks during this sequence that she "believe[s she] understand[s] I understand now just who and what [Midna is]". The picture she goes on to paint of Midna is unselfish, and describes more regard of Midna's for Hyrule than Midna had previously demonstrated in her attitude. This is the final event which causes Midna to vocalise a desire to save Hyrule as well as the Twilight Realm, and is a key event both in her character development and in the relationship between her and Zelda.
Towards the end of the game, it is revealed that Midna had been harbouring Zelda's spirit inside of her: for once, light and shadow had mingled. This in itself may also have influenced Midna's feelings towards Hyrule, recognising that she and Zelda were not antithetical but complementary — as vocalised by Zelda as Midna departs finally for the Twilight Realm.