Если совсем поджимает время обработки, то обычно советуют использовать шаблоны. Есть даже примеры, когда эти файлы-шаблоны в бинарном виде храняться где-нибудь (в ресурсах, в базе данных — в бинарных полях), а потом вынимаются от туда, создают файл-шаблон на диске и его уже открывают — т.о. шаблон всегда с тобой.

Для убыстрения Excel'я можно еще такие настройки применять:
Application.Calculation = xlCalculationManual
Application.EnableAnimations = False
Application.EnableEvents = False

Ну и большое значение конечно имеет сам код форматирования — это целое поле для деятельности. Чем меньше будет лишних вызовов и обращений к ячейкам, тем лучше, ну и конечно никаких .Select Так что, код в студию