What do you use to get your email? Do you index it? The last time I tried using Gnus it used to take more than a minute to start up and I really don't think I have that much mail, although I am subscribed to 10+ mailing lists.
This results in pretty fast gnus startup times. But then, I only start it up every once in a while when I have to reboot due to a kernel upgrade.