Je hoeft alleen degenen uit te sluiten die directe vrienden zijn, maar ook vrienden van vrienden. Ik heb de tabelaliassen herschikt, zodat het een beetje duidelijker is (voor mij in ieder geval) wat er wordt opgehaald:
SELECT
u.*
FROM
user u
INNER JOIN friend ff ON u.user_id = ff.friend_id
INNER JOIN friend f ON ff.user_id = f.friend_id
WHERE
f.user_id = {$user_id}
AND ff.friend_id NOT IN
(SELECT friend_id FROM friend WHERE user_id = {$user_id})
Het verwijdert ook de noodzaak om de gebruikers-ID die wordt opgevraagd uit te sluiten.