When I turn the phone off, then turn it back on. It takes about 10 seconds to start back up, doesn't seem overly long to me. I've never really thought about how long it should take. Also note that I have only 8 Apps installed on my iPhone.
I haven't had to do this with my iPhone 3G. But with my old iPhone, I had to do this a few times. Mainly when it handed off from wi-fi to a weak edge signal for some reason. It did seem to take a minute or two to reset.