LIMIT quindi RAND anziché RAND quindi LIMIT

Puoi farlo usando una selezione interna. Seleziona le prime venti righe nella selezione interna. Nell'esterno seleziona queste righe in modo casuale e seleziona le prime cinque:

SELECT *
FROM (
    SELECT *
    FROM table1
    ORDER BY score DESC
    LIMIT 20
) AS T1
ORDER BY RAND()
LIMIT 5