Here is my take on it.
Navi is Link's friend, she's the only one who shared that big adventure with him, experienced his hardships, fought with him in every battle. She's the only other one who remembers what happened after they go back in time at the end. They had a very strong bond because of that, but she couldn't stay with him. He's not a Kokiri, and the rules of the forest or something wouldn't let her. She cared about him a lot, and I doubt she really knew in the beginning that this arrangement was temporary, she seemed as surprised as Link by all the things that had happened. I see her leaving so suddenly as a sign of how difficult it was, because she knew if she prolonged their goodbye it would only be more painful for both of them.
And Link, imagine how he must feel. He's been an adult even though he never experienced growing up, and now he's a little kid again so he can have his youth back, but after all that there's no way he could go back to being carefree. He's trapped somewhere between a child and an adult, he's both and neither. He was always different, but now he's truly alone, no one else knows or understands what he's been through. He must have thought that if he could find Navi she could still be his friend, or maybe he just wanted to talk to her one more time. And who knows? Maybe after Majora's Mask he does find her again, even though she couldn't be his partner, at least he might see her again.
"Whenever there is a meeting, a parting is sure to follow. However, that parting need not last forever... Whether a parting be forever or merely for a short time... That is up to you."
