Fi wasn't annoying at all. Being completely devoid of any personality (having the emotional scale of a robot) was the best possible characterisation for a sidekick who's basically a sword. Swords aren't sentient and Fi was the spirit of Master Sword, thus she didn't have any feelings. She was created by the Goddess, had only a single purpose to aid Link in his quest (though yes, informing that the batteries are running low on every possible moment while you have that "low battery" icon on the bottom of the screen did strike more as Nintendo being the mother hen to all gamers than "an annoying character quirk" to me).
I would have found it odd to have another sidekick with huge personality and humongous back story (like Midna, who stole the limelight from other characters every now and then), especially this time when the sidekick is a spirit of a weapon. Master Sword had, in that sense, humbler origins when its past only involed its creation and Fi, who somewhat emotionlessly followed through with her orders. It was a perfectly logical personality.
She's the new Navi in the sense that she was the new sidekick, who informed Link on where to go, what he was fighting etc. In a way I think OoT!Link and Navi developed more close friendship than SS!Link and Fi, due to differences in their stories (and clearly because of Fi being...Fi). But both OoT!Link and SS!Link felt bad after parting from their sidekicks. Still, annoying? Meh, Navi always seemed more like "that one nagging friend" to Link than an actual annoyance.
Besides, I think it's...safer to have Fi being in the Master Sword than, say, Ghirahim. Who knows what kind of Lady Gaga-esque shenanigans he'd pull. He'd steal everyone's attention. : D