I've gotten pretty good at writing fast interfaces with Excel; the main point to keep in mind when writing code that's building a spreadsheet is to talk to Excel as little as possible. In other words, batch together as many "transactions" as you possibly can. Each transaction tends to take an appreciable amount of time, at least when you start having thousands of these transactions.
So, the main thing I try to do in building worksheets is just to store all the data I'm going to write to Excel in a 2D variant array, then you can just dump in every formula/value at the same time. Works great, makes building worksheets pretty fast. There's lots of articles online talking about how to do this.
Unfortunately, Excel doesn't expose this same functionality for other aspects of cells, like Interior.ColorIndex. I believe you can build a big, non-contiguous range and apply the Interior.ColorIndex property to that whole range, but that just shifts the transactions to building the non-contiguous range, which is just as slow as setting the ColorIndex on each cell.
One other thing I usually do is turn off calculation and sometimes graphic updating, and that can save a bit of time.
In this recent project, I had to work with inserting columns, and was getting frustrated that Excel 2007 was taking around 200 milliseconds to insert a column. The weird part was that 2010 did not take that long, so I figured it was something Microsoft fixed for 2010.
Long story short, I found an Excel blog talking about coding best practices for Excel VBA, and they include disabling events and the status bar on top of turning off graphic updating and calculation. So I turned off events and status bar updating, and that somehow fixed the problem, bringing down the column insertion time to less than a millisecond. I don't know what the issue was, maybe some addin sitting there thinking about me inserting columns and blocking my code from continuing, but no longer.
This post is mainly so any poor soul who (like me an hour ago) starts searching for help on Excel 2007 being slow inserting columns, they'll see what worked for me.