Как узнать почему.NET служба долго запускается?
В 2012й студии есть встроенный профайлер, скрывающийся в меню ANALYZE. Из сторонних - можно использовать dotTrace.
В любом случае, прежде всего лучше переписать службу так, чтобы она могла запускаться как консольный процесс. Если еще и вывод лога в консоль добавить - то многие вещи можно будет увидеть визуально.
Пишите в журнал событий логи и найдете где затык