"I was blown away by how good facebook's recommendations for friends were..."

Search online for 'Facebook shadow profiles' to get an idea of why this was so good. It's more than just your phone number.

Edit: And you also say "Use a different app for instant messaging" but (since you're going for the privacy approach) that should not be WhatsApp and photos should not be via Instagram. Most people have no idea that these are both Facebook properties.