Hoping to solve this since it seems once people solve it, they stop posting.
I upgraded from Tiger to Leopard using the upgrade/update option. Not the archive install, not the erase and install. I went from 25s boot time to 70s boot time, and while Tiger was ready to go after it's 25s, Leopard needed another 40s after boot before apps started (much like my win xp can). At 110s I was horrified. I checked this thread, cleaned cache, cleaned up desktop and shaved a good 15s off the total time, but it was still horribly slow and I was considering sticking to Tiger and leaving Leopard in it's box, but...
Solution:
After further reading on forums, I tried this:
I backed up all my stuff.
I did a clean Erase and install.
After reinstalling my apps and files I've got a boot time of 30s (of which 5s is annoying bluescreen with arrow) and after that apps start instantly. This is a 5s increase, and I can certainly live with that.
In short. Don't update your Tiger system, backup your files and do a clean erase and install and it'll work like a dream.