MySQL ORDER BY rand(), nome ASC

Usa una sottoquery:

SELECT * FROM 
(
    SELECT * FROM users ORDER BY rand() LIMIT 20
) T1
ORDER BY name 

La query interna seleziona 20 utenti a caso e la query esterna ordina gli utenti selezionati per nome.