Thinking about it, you arleady said it's earlier on than when this stuff matters.
IGNORE THIS CRAP:
So what programs startup with windows?
Start > Run
regedit > OK
HKEY LOCAL MACHINE > Software > Microsoft > Windows > Current Version > Run
Those are the other things that startup with windows other than what windows needs. There can often be crap in there that's unnecessary.
MILDLY RELEVANT:
If you've reinstalled Windows, and it booted up slowly with a fresh install, something is probably very wrong. Have you got any way of swapping out parts to see if something inparticular is causing the problem? (Ram, CPU, etc)