One common mistake that I've found is that shops basically have IBM i set up for interactive use. In other words, they have a subsystem (often QINTER) where they do almost all of their processing, so they have their memory pools set up to give QINTER pretty much all of the memory.
As the workload changes, and more work is done in the HTTP server (tho, i guess this philsophy applies to other things too, like SQL) they don't consider the fact that the memory is all allocated to interactive.
This is particularly true for my customers (I work for Profound Logic Software) where they might transition away from 5250 interfaces all together, and then do the same type of work in the more modern web interface. They complain that it runs slow, but when you look at it, you see that the problem is just that they have all their memory allocated to the (now unused) 5250 subsystem. Simply re-allocating it to the HTTP server makes the performance more or less equivalent. (Tho, web does use a bit more memory, it's not usually too much -- and memory is cheap, at any rate.)
So.... that's my suggestion. Take a look at your memory pool allocation. Maybe even consider adding some memory to the system. That's usually why you get those long startup times.