As a word of caution, I believe you can do online index rebuild only with the Enterprise Edition of SQL Server. If you have EE, great. If not, taking down the index on a very large table will most likely result in the table being effectively offline. You aren't going to efficiently query 3M rows without lots of disk I/O.

If the table has to remain online, consider reorganizing the indexes instead of rebuilding. Doing a rebuild generally yields the best results, but reorganizing is sometimes necessary.

Another word of caution, if you alter your clustered index, all nonclustered indexes will be dropped, then the clustered index is changed and built, then nonclustered indexes get recreated. This is necessary because the clustered index gets inherited in by all the nonclustered indexes. This can take considerable time and should always be tested on a test system first.

I completely understand being under the gun to get something fixed, but please don't rush too much. Think it through, make sure you understand how it works and test it out.