I find her only annoying during side quests. I hate it when I am trying to do something away from the main quest and she keeps on telling me where to go next. Other then that I don't find her to be too much of an annoyance.
She has never annoyed me much, but she does get on my nerves a little bit. Like when I already have the boots on, and I'm almost too the final boss in the water temple, I think she might have some important information after the long hey listen thing, I click ^C and do you know what she says? "you should see what happens when you try on those boots in water!" (or something along those lines) Which she already told me at the BEGINNING OF THE TEMPLE. AS I'M WEARING THEM TO GET INTO THE TEMPLE. Other then that one time she did that (which gave me a little bit of a giggle with a side of annoyance) she never really bugged me much. But I asked someone who was staying at my house for the summer (who has never played the games, but he has watched me play) he said that she was very annoying. But then again, he gets annoyed very easily.
At least in OoT 3D the text moves faster, so from Navi telling you basic things that you can't skip in the Deku Tree to Kaepora Gaebora, it's not nearly as annoying. I only get annoyed a little with her when I know where to go next, but I'm busy doing other side quests and how she keeps telling me. Not enough to become aggravated, however.