Honestly, Navi isn't as annoying as people say, but she still annoys me a bit. It's not that she says "HEY! LISTEN!" all the time, it's the fact that when she says it, I won't be able to press Up-C to look around without having to listen to her. Sure, it's completely optional, but I always look around with the first-person camera in every game I play, I enjoy seeing everything around me. It's even more annoying because, despite giving information, most of it I know already or really don't care at the moment. As for enemies, I never used her, instead I would just swing my sword and stuff would die, so she really didn't help with those, either. Just to add more to it, she never was all that amazing to me as a character, the only thing she did that made her seem more like a character and less like "That fairy who tells you about things." was during the final battle. (Of course, there's a chance I'm wrong here, I haven't played the game in a year.)
I've seen Kaepora Gaebora brought up a bit in this thread, too. He's actually not that annoying to me, that's because if I really don't want to read what he says, I just press B once and it skips through everything. He's too easy to deal with and isn't seen often enough to be annoying to me.
However, I think Navi is annoying. Not as annoying as a lot of people say she is (Despite how it seems from what I typed up.) but still annoying.