Chunk any overly long install queues and set the requested package to check for dependencies and add itself to the next chunk, after the current chunk is processed.
It needs improvement, sure, but I still don't see it as a UX killer, especially when compared to most commercial install and update systems.