a) Do a search for Boot Log Analyzer on Google, or your favorite search engine. Download the program (it's shareware or freeware, not sure which) and then reboot, hit F8 to get to the Windows start-up menu, and select option 2, so it creates a bootlog.txt file. After booting, launch BLA and open your bootlog.txt file. See what options are taking a long time to load. More than likely, something in there will help identify your culprit.
b) Edit your Internet properties (2 ways are either through Internet icon in Control Panel, or when in IE, use pull-down menus for Tools, Internet Options) and click on the Connections tab. In the middle of the screen, change your options to Never dial a Connection. You'll still be able to dial your ISP when needed, but this will prevent the system from trying to connect automatically. If you have Active Desktop enabled and you really don't need it, turn it off. It might be causing Windows to look for a connection, too.
c) (Don't think this will help at all, but sometimes strange things happen) Check your network settings and see what is listed for the primary network logon. If it isn't already, set it up as Windows Logon.
d) boot to a Windows 9x startup disk and when you get to the A:> prompt, type FORMAT C: /S /Q. (Just kidding!)
Use option A because that program is handy to have. However, try "option b" BEFORE rebooting. This way, when you reboot to create a bootlog.txt file, you'll also be able to see if that fixed your problem. You can still analyze the bootlog.txt file to see if anything else is slowing you down, but you'll save yourself a reboot by doing A and B at the same time.
I think you'll find that B is causing your problem. I wouldn't put money on it, but it is a strong hunch I have. Let us know either way, so that if someone else has this problem, they'll see what helped you.