Disclaimer: I'm still not sure I understand fully what setup.py does.
From what I understand, using a setup.py file is convenient for packages that need to be compiled or to notify Disutils that the package has been installed and can be used in another program. setup.py is thus great for libraries or modules.
But what about super simple packages that only has a foo.py file to be run? Is a setup.py file making packaging for Linux repository easier?
Using a setup.py script is only useful if:

Your code is a C extension, and then depends on platform-specific features that you really don't want to define manually.
Your code is pure Python but depends on other modules, in which case dependencies may be resolved automatically.

For a single file or a few set of files that don't rely on anything else, writing one is not worth the hassle. As a side note, your code is likely to be more attractive to people if trying it up doesn't require a complex setup. "Installing" it is then just about copying a directory or a single file in one's project directory.
Should every python program be distributed with a setup.py?