App created with PyInstaller has a slow startup

Tell PyInstaller to create a console-mode executable. This gives you a working console you can use for debugging.

At the top of your main script, even before the first import is run, add a print "Python Code starting". Then run your packaged executable from the command line. This way you can get a clear picture whether the time is spent in PyInstaller's bootloader or in your application.

PyInstaller's bootloader is usually quite fast in one-dir mode, but it can be much slower in one-file mode, because it depacks everything into a temporary directory. On Windows, I/O is very slow, and then you have antiviruses that will want to double check all those DLL files.

PyQt itself is a non-issue. PyQt is generated by SIP which generates very fast lazy bindings; importing the whole PyQt is faster than any other GUI library because it basically does nothing: all bindings to classes/functions are dynamically created when (and if!) you access them, saving lots of memory too.

If your application is slow at coming up, that will be true without PyInstaller as well. In that case, your only solution is either a splash screen (import just PyQt, create QApplication, create a display the splashscreen, then import the rest of your program and run it), or rework your code. I can't help you much without details.

I suspect that you're using pyinstaller's "one file" mode -- this mode means that it has to unpack all of the libraries to a temporary directory before the app can start. In the case of Qt, these libraries are quite large and take a few seconds to decompress. Try using the "one directory" mode and see if that helps?