Merge, shuffle, and paginate
Got some help and finally got this working. Here's the final code for my future self and anyone else that may need this: 

{% set thisService = entry.slug %}
{% set shufflePremium = shuffle(craft.users.group('premium').search('counselingServices:' ~thisService).ids()) %}
{% set shuffleBasic = shuffle(craft.users.group('listed').search('counselingServices:' ~thisService).ids()) %}
{% paginate craft.users().id(shufflePremium | merge(shuffleBasic)).limit(16).fixedOrder(true) as pageInfo, members %}

{% for user in members %}
  (...)
{% endfor %}