Funny. Isn't that more or less the same as the start of Facebook?
I do assume that only active users do pop up in the app. (created a post or comment in the past x days)

When a user is logged in, you could present names which are on the following list or with which they had an interaction in the past 30 days. You could update those lists once a day.
This way it is more likely that people do know both in the choice.
Just some thoughts.