I am also having this problem and am getting VERY annoyed with it. The delay on my box (Duron 800, Riva TNT) is only about 20 seconds, but there's something odd about my machine during this delay.
For example, I run several programs at their maximum priorities (renice'd to -20). If I do anything with my computer, those programs still work fine (video/audio capture from my TV card, BTW). However, during the delay while X is coming up, even the highest-priority processes stop functioning for several seconds.
If I use the "nv" driver from XFree86, I can stop and restart the X server and the process runs fine without dropping a single frame.
The capturing programs also drop frames when I am switching between X and the console (again, only when using nVidia's drivers).
I did the remote "top" while X was starting and the program did not update the display for several seconds (probably again related to the nVidia delay). When it was updating again, "X" was at the top with 95% CPU.
Lastly, I tried running an older kernel module (1.0-1541) along with the latest GLX. To my surprise, this works, but the huge delay remains. Because of this, I believe the delay is caused by the closed-source GLX libraries. If I use the older GLX installations, the delay is lessened.
PS - Is anyone with a TNT/TNT2 NOT having problems with a delay (10-60 seconds) when starting X?