IDentify the long running queries. Identify the columns in the WHERE condition of those queries. Do you have indexes on all/most of those columns? Also, do you have regular maintenance jobs re-indexing/updating stats for that table.
is this large table written to often, or only read from? if you only read from it, you can add appropriate indexes without penalty to improve the selects. use profiler to find out which queries are slow, then have a look at the query plan of those selects to see what indexes would improve them.
alternatively you can try the index tuning wizard, see what it suggests.