Hmm, with Pyinstaller I generate true standalones which require no libs at all, nor Python to be installed on the host system. Do you use the --onefile option?
As an example, here's a little project which I also release as a single binary file that works everywhere I've tested, with no deps: