Long Delay's Connecting to Network

In our organization we use an assortment of PC platforms (mostly Win2k, NT4.0, and 98SE) on a NT4.0 Server based network. We utilize DHCP to supply IP's.
On certain computers - regardless of operating system - it takes a LONG time to connect to the network. After reboot, 2k machines will begin to load Windows and sit at the 'Preparing Network Connections' for 30-40 seconds, then finally finish loading. This only occurs after a reboot or if the machine has been off. A simple log out and log inwill not duplicate the problem (I assume because the connection is still there). A bigger problem occurs on Win98 machines, where-in the user will reboot the PC, and immediately try to log in. They will then get the error that no DNS Server was available and so on, but if you have them cancel (or log back off) and try again, it will go right through.
I remember a question that was posted earlier on this site that was somewhat similar, and one answer was to look at DNS settings. I checked these, but they made no difference on the Win2k machine I was working on. (I tried everything I knew about setting up DNS - It wasn't enough or I don't know enough!)
One other thing....
I have watched our switches as nodes power up. We have Cisco Catalyst switches (2900's, 3500's, and 4000's)It goes through a handshake process - or auto-negotiating that sometimes takes up to 10-15 seconds. But I do not understand this delay in a select few computers.
The cables check out, their is not a significant amount af broadcast traffic, and errors are not present.
Any suggestions?