Me too...
Just as a point of reference, I too have similar issues. I have never been jailbroken, though do have all 11 pages full of apps. Still, I have about 10 gigs free on a 32 gig iPhone 3GS. Boot time or reboot time for me is nearly 10 minutes. I rarely ever reboot except when flying, but it is an extreme pain when necessary. If I recall correctly, I did not have this problem when the phone was new. Not that big of a deal since I rarely need to reboot, but still a huge inconvenience when a reboot is in order.