That is not normal and definitely not the way it should be. My 1GHz FP iMac needs like < 10 sec to get to the blue startup screen and then it takes maybe < 15 sec till the logon window appears.
Check that the Mac isn't looking for a network connection that isn't there anymore, like Ethernet selected in the system prefs, but no cable connected.
Also, check that you have selected a startup system folder in the system prefs. If none is selected the Mac will first look for one on all connected devices, which can take a while. Although I thought this is what causes stalls during the blue startup screen, but if I understand you properly the lag is during the grey startup screen... Strange.
Try booting OS 9. Does it also take as long to get a happy Mac and then the "Welcome to Mac OS" screen? If no I would guess your permissions and/or your OS X installation are screwed.