One way to deal with creepiness of friend requests is to not have them "mutual". Friendship in real life is one-sided relation and so could be on a meet-new-people platform.

This is one of the insights that we have used at Chatimity (www.chatimity.com) - for building a place for making new friends online. It is like old style chat rooms but much more civilized due to a good amount of behind the scenes measures being put in place. We have had fair bit of adoption and continue to flesh this out more.