LIMIT potem RAND zamiast RAND potem LIMIT

Możesz to zrobić za pomocą wewnętrznego wyboru. Wybierz dwadzieścia górnych wierszy w wewnętrznym zaznaczeniu. Na zewnątrz wybierz kolejność losowo tych wierszy i wybierz pięć pierwszych:

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