3 млн. записей не так много. Видимо надо посмотреть есть ли индексы на страницах, перестроить статистику, оптимизирован ли запрос на выборку, выбирать не все 3 млн. ил 100 тыс, а тысячу, кэшировать их, отображать юзеру 20 - 50 записей, использовать пейджинг.

Можно конечно и увеличить время ожидания ответа, но 10 минут это не нормально.

Со временем работа с индесами становится медленнее, условно говоря из-за того, что данных становится больше и первично построенные индексы, расчитанные на малый объем данных, плохо справляются с большим объемом.
Для перестройки статистики есть команда UPDATE STATISTICS, как ей пользоваться см. в SQL book online.

Пейджинг, имелось ввиду отображение данных пользователю по странично ,например по 20-50 записей, сперва первые 50, потом вторые с 50 по 100. Для этого можно использовать грид в АСП.НЕТ. Есть несколько вариантов как реализовать такое отображение ,например использовать хранимые процедуры выбирающие данные порциями, или вытащить 1000 записей в DataSet, положить их в кэшь и брать оттуда.

Еще советую посмотреть в QueryAnalizer Execution Plan, выбрав его в меню Query, он покажет где тормозится запрос. Единственное, что с Execution Plan -ом надо уметь работать.

Можно и асинхронно выпонять запросы, но все это уход от основной проблемы.