Exatamente como o gustavo comentou. Cuidado com muitas idéias de uma vez só. Mas na verdade a indexação acaba sendo uma verdadeira e interessante arte. Pense também nos inserts. Como você comentou que a tabela é grande, me parece que recebe muitos inserts. Lembre-se que em qualquer insert e update você estará atualizando indices também. Tente sempre encontrar o melhor conjunto de indices para seus selects sem contudo atrapalhar os inserts e updates (falando de desempenho). Exitstem muitas técnicas para que voce possa alanizar as melhores colunas para indices como por exemplo DBCC SHOW_STATISTICS ('Tabela', 'Coluna') onde você irá analizar densidade/seletividade de suas colunas, desde que se tenha estatísticas criadas. Para mais informações aqui no msdn voce encontra nesse link: http://msdn2.microsoft.com/en-us/library/aa258821(SQL.80).aspx
Bem... discutir sobre como escolher indices é interessante mas esse é um ponto que pode te ajudar em outros casos.
Mas lebre-se de não carregar muito sua tabela com indices e principalmente não crie um indice para cada situação que possa surgir na vida. Exceto, claro, em algumas excessões. E o que viria a ser um grande número de índices? Em um dos sistemas críticos onde administro atualmente, encontrei uma tabela que o desenvolvedor resolveu criar um indice para cada select que lhe passava pela cabeça. resultado: 71 indices em uma tabela aki, 10 indices em outra tabela ali (sendo essa a tabela "chave" de todo o sitema, com muitos inserts e muitas consultas).
Ok?
