Order by related entries count
Any native solution is likely to be slow - I would recommend using the Preparse field plugin.

It lets you use Twig to dynamically generate a field at the time an entry is saved — you could have Preparse count up the number of related users on save, and then sort by that custom field.