Na verdade... acabei fazendo um teste e talvez tenha respondido minha própria pergunta. Eu pensei em postar esta informação aqui no caso de ser útil para mais alguém. (Se eu fiz algo errado aqui, por favor me avise!)

Isso é meio surpreendente...

Ao contrário de tudo que li, criei uma tabela chamada TestData com 1 milhão de linhas e executei a seguinte consulta:

SELECT * FROM TestData WHERE número =41 ORDER BY RAND() LIMIT 8

...e retornou as linhas em uma média de 0,0070 segundos. Eu realmente não vejo por que RAND() tem uma reputação tão ruim. Parece bastante útil para mim, pelo menos nesta situação em particular.

Eu tenho três colunas na minha tabela:

identificação [BIGINT(20)] | campo de texto [tinytext] | número [BIGINT(20)]

Chave primária no id, índice no número.

Eu acho que o MySQL é inteligente o suficiente para saber que só deve aplicar RAND() às 20 linhas que são retornadas por "WHERE number =41" ? (Adicionei especificamente apenas 20 linhas que tinham o valor 41 para 'número'.)

O método de subconsulta alternativo retorna resultados com um tempo médio de cerca de 0,0080 segundos, que é mais lento que o método sem subconsulta.

Método de subconsulta:SELECT * FROM (SELECT * FROM TestData WHERE número =41) as t ORDER BY RAND() LIMIT 8