Для того, чтобы узнать, находится ли конкретный пользователь в сети, первый способ будет намного быстрее - нет ничего быстрее, чем чтение одного ключа.
Поиск пользователей на определенной странице не так очевиден (я не видел четких цифр производительности клавиш пересечения или подстановочных знаков), но если набор достаточно большой, чтобы вызвать проблемы с производительностью в любой реализации, это не так все равно практично показывать их все.
Для сопоставления пользователей со списком друзей, я бы, вероятно, пошел и с первым подходом - даже несколько сотен операций get (проверка состояния каждого в списке) должны превосходить пересечение на нескольких множествах, если эти множества имеют большое количество записи и трудно поддерживать.
Наборы Redis больше подходят для вещей, которые нельзя сделать с помощью ключей, особенно когда получение всех элементов в наборе важнее, чем проверка, находится ли конкретный элемент в наборе.