SQL server performance and tuning I am working on a system, there is a cisco load balancer that can handle 40K requests.

There are two app servers. There are 12 or so web services. 

and there is a SQL server with 2TB of data.

Bottle neck here is SQL server, it is on a single machine with Quad Core CPU, and 80 GB ram. 

There are about 2.5 million items stored in database. 

The kind of queries are , select product with some properties which are not indexed.

There is a huge index and we don't want to index everything, because index fragmentation is really hurting performance.

I thought about caching, distributed caching, but some of the queries are not very convenient for caching, such as give me companies that starts with foo. There is a huge combination there. 

How would you go working on this issues?

There is more select than insert. mostly select. There are several small select. and there are some joins with 3 tables.
With 2.5 million items I would expect your indexes to be rather large.  Particularly if you are indexing on large fields.  Also just as an FYI if your primary key is large that doesn't help either.  Any non clustered index has the primary key (assuming that is your clustered index) in it regardless of if you include it or not.  It has to as a reference back to the table.

So if you have a large primary key (and only if you have a large primary key) you might consider creating an identity column and changing that to your clustered primary key.  You can keep your existing primary key as a non-clustered unique index.  Also if you are worried about index fragmentation REBUILD/REORG it.  It's part of the ALTER INDEX command in SQL 2008 and up.  You can even do it on line.

My suggestion to you is to add the indexes you need (within reason).  Generally 3 or 4 non clustered indexes isn't going to hurt performance.  Honestly you can probably get away with 10 or so without a problem if you really need it.  Test on your system as mileage may vary.  Personally I would make sure that you have a clustered index as well.  Also add a maintenance job of some type to do your index REBUILD/REORG.  There are a number of them out there that will even check your current fragmentation and REBUILD or REORG intelligently as needed.