I honestly don't find her all that annoying, though I suppose I can understand that if you're replaying the game and already know what to do, she's pretty much stating the obvious. But her "nagging" isn't really that bad if you do what you're supposed to do when you're supposed to do it. I think the thing that bothers me the most is her name flashing on the HUD when she has something to say. I have ADHD, and seeing flashing can be a little distracting for me. I was also bothered by the life meter, when the current heart beating, was introduced to the series.
Sidequests can be a little annoying, simply because Navi is reminding you to take care of something else, but knowing me, I probably need that. Again, I can get distracted by things pretty easily, so I don't mind the occasional reminder that Navi drops my way. I really don't have a problem with her, but I suppose some people have the need to hate on her because they think that makes them "cool". Navi is a cute character, and the change in the style that which the fairies were designed was a fresh change to the franchise.
I say, if she's annoying to you, just put her in your hat. xP