Created flag for "add friend", set a View, works but there's a problem Ok, so now when a user looks at HIS profile, he gets the links to HIS list of friends, great!
However, when the same user looks at someone else's profile, he sees the links and they point to THAT user's friends - and I don't want that...

I'd like the 'friends' link to only appear if I'm seeing my own profile page; when looking at someone else's profile I shouldn't be able to see THEIR list of friends.
It sounds like your view is already set up with the proper Flagged: Node relationship and "User ID from URL" contextual filter.  If you edit the view and then edit the Flagged: Node relationship, you can try checking the box for "Only display if flagged by the currently logged-in user" and see if that helps you.

Keep in mind, this method will still display people that were flagged by both Person 1 and Person 2 (common friends, in other words).  Another solution would be to have a private profile page and a public profile page, with different views on each; you might want to look into the Profile2 module.