Navi has a lot of un-deserved bad rep for constantly saying "Hey....Listen", The only thing I found annoying about Navi was when she forced you to listen at the start for small things like how to open a door

.....I'm pretty sure over the 10+ years Link has been there he opened a door.
Navi also doesn't add anything to the story, But if it were not for her we would have recieved a different sequel, She is the reason MM was made the way it was. Which is a plus but then again I think that the game would have been made just as good.
I prefered Midna much more, She looked good and was excellent compared to Navi, Navi was just a glowing orb with wings, Midna was an Imp like creature who could emotion which added to TP's Story.
Midna also added a lot of depth into TP, Her cutscenes were very good where as Navi's weren't so good. Navi always seemed calm other than 2-3 times, Midna was getting more angry as the game got on which I liked. It built up even more depth to the game.
She had powers that helped Link in his Wolf Form. In OoT you could warp around using the Ocarina of Time, Although the music was a loss to TP Midna was the reason you could warp around Hyrule.
Navi didn't really do much, She gave you a fair amount of useful hints throughout the game but they were out weighed by the amount of useless one's she gave you about everything. She didn't add any depth to the story really.
Then at the end Navi ran off with out much explanation, All I can remember is her just running off, If I remember correctly the reason she left was lame. Midna left because she feared letting what had happened to fall on Hyrule again because of her own people. I liked her ending as well, It was not running away but leaving for the sake of Hyrule.
As you can see above this is why I much prefer much...