Keep it simple.

select *

from table1

where criteria1 = TRUE

order by random()

limit 500

Simple enough to get the job done and pulls a random sampling based on the result set.