Сергей Наумов

1. Как сравнить не используя = -- вопрос риторический.
даже не буду спрашивать для чего :-)

2, Определяем индекс текущего дня недели: SELECT DAYOFWEEK(now())
0 - вс, 1-пн, 2-вс и т.д.
а дальше -- если это меньше или равно 2 -- (до вторника включительно) -- прибавляем 2 - полученный индекс дней
а если это больше 2-х -- прибавляем 10- "индекс" дней

То есть, примерно так на мускуле:
select if(DAYOFWEEK(now())<=2,from_days(to_days(now())+2-DAYOFWEEK(now())),from_days(to_days(now())+7+3-DAYOFWEEK(now())));

Сортировка по вычисляемому полю будет работать долго априори.
Для того, чтобы ускорить такую сортировку -- сделайте дополнительное поле в таблице, создайте индекс и делайте периодически:
UPDATE table SET srt_field = ifnull(r.time_pay_for, r.time_update);

Вместо периодических апдейтов можно использовать и триггер.

Вариант 2 верный.
Не стоит бояться кол-ва записей в таблице.
В случае правильной оптимизации базы (создания индексов нужных индексов и верного построения запросов) всё будет достаточно быстро работать.