Bueno, para esa cantidad de registros se utilizan los indices en tu tabla, esto para mejorar la velocidad de busqueda. Ahora si todas las transacciones seran locales, es decir en una sola maquina, es mejor que utilices una consulta directa a sqlserver.

Por otro lado, no es recomendable mostrar todos los datos de golpe, deberias hacer que tu consulta tenga buenos parametros de filtrado, para de ese modo reducir la cantidad de registros devuletos en una determinada tranasaccion.

En pocas palabras para tu caso, me qudo con la opcion de hacer consultas directas a la base de datos.

Saludos


PD:
Indices en sqlserver
http://www.sqlteam.com/article/sql-server-indexes-the-basics