Most people who complain that Navi was annoying played OoT 10-10,000 times, and they heard her talk 100-1,000,000 times.
The only reason she's annoying to today's generation of gamers is because most gamers today have played newer 3D Zelda games, then they played OoT, and already knew how too "Open doors with the 'Action Button'" or that they "can't breathe underwater". But what you have to remember is that most gamers back in 1998 thought that OoT was the best thing known to man because it was 3D. It was also the first 3D Zelda, so they didn't know about the "Action Button" or that they couldn't breathe underwater, because in LA, the game automatically took you back up when you couldn't breathe. They also didn't know about the Water Temple, bless their souls.
Now Tatl, on the other hand, was basically a meaner Navi. She had the exact same purpose, telling you stupid stuff. Although you didn't need to know it because you already knew about it. Because between 1998 and 2000, gamers probably played OoT 20 times.
And then, there's Kaepora Gaebora....again, bless the 1998 gamers' souls. That's all I have to say about that.