Насколько индекс ускоряет выборку с условием-неравенством?

Будет ли этот запрос быстрее работать, если для столбца `time` есть индекс?

Зависит от того, какой процент записей отбирается запросом. Если менее 5-7%, то скорее да, чем нет, иначе нет.

Optimization and Indexes - изучи внимательно. Там много полезного.

Вообще насколько целесообразно делать индексы на все столбцы, которые есть в условии выборки и в которых много уникальных значений?

На все - это отдельно на каждое поле, или речь о композитном индексе? Первое, как правило, бессмысленно, все равно будет использоваться не более одного из всех индексов.