After scouring the forums over at MacFixIt and googling my brains out, I think I finally fixed the problem I have been having with the Mac. It appears that either my cache data or prebinding data got munged somehow and was causing the “30 seconds to start” problem. Fortunately I discovered a nearly-free tool named Jaguar Cache Cleaner which is able to correct both problems… After mucking about with several similar tools I found this one to be the cleanest to use.. After it rebooted my machine I launched every application in my dock and all started pretty fast, with all applications getting the “hey this application is currently running” arrow in the dock within a second or two (until ram started to become scarce, then they took a few seconds to appear). When I was having this problem, the icon would bounce in the dock for 30-60 seconds before I even got the arrow!
So the moral of this story is that if you beat your head against a problem long enough you can eventually fix it. The more important moral of this story, however, is that Apple still has some de-sucking to do in their fancy little OS.