Если вы используете MySQL, вы можете произвольно заказать все записи, которые соответствуют критериям больше, чем критерий, и выбрать верхнее n.
Фактический запрос будет выглядеть как
SELECT * FROM posts WHERE votes >= x ORDER BY rand() LIMIT n
Не проверял это, но что-то вроде этого должно работать в Rails:
Post.all(:conditions => ["votes >= ?", x], :order => "rand()", :limit => n)