py2exe
py2exe is a tool for making standalone Windows programs in Python:
py2exe will compile your Python script, and any Python code or modules you use, and combine the compiled Python with a wrapper (written in C, I think) into an executable.
The .exe file still needs the Python DLL, but it's pretty close to a single executable.
The fact that py2exe only takes the Python code that you use means that you don't have to include the whole Python standard library. The executable will function without Python being installed, and it will function alongside existing Python installations. It needs to know if you use any external DLLs; if you do dynamic imports of modules, you may need to explicitly declare them to py2exe.
I've used py2exe and InnoSetup to do a self-installing .exe for a Python shoot-em-up game I wrote. It works great.
InnoSetup
Regarding deploying Python apps on Windows, I've had very good luck with that. You can make decent apps that you can make into a self-extracting executable, that will easily fit on a floppy disk. If you use external DLLs, of course, they will add to the total size.
To make a self-extracting .exe file, I use a fantastic free (GPL'd) setup program called InnoSetup:
InnoSetup is just amazing-- very high quality software, with a setup wizard that does almost everything for you!
Gordon McMillansInstaller
I've also used GordonMcMillansInstaller for another app-Installer also works well (same output as py2exe) but is a little harder to set up. One thing that Installer can do, that I don't know if py2exe can do, is make a single executable file, rather than calling an external Python DLL.
Also, see April2006Notes for pointers to other distribution/install tools.