Gebruik een subquery:
SELECT * FROM
(
SELECT * FROM users ORDER BY rand() LIMIT 20
) T1
ORDER BY name
De binnenste zoekopdracht selecteert willekeurig 20 gebruikers en de buitenste zoekopdracht rangschikt de geselecteerde gebruikers op naam.