You're not alone in being irritated, this is Python's biggest weakness.
Py2Exe, which you tried, is pretty standard for doing what you want in Windows land; unfortunately it's a not simple one-click to do. If you're having trouble, you might want to read up on the unhappy state of python distribution tools and also look further at the way setup.py's are structured.
There's not necessarily one right answer here, but there are some important parameters to think about:
1) Do you care about having a working python interpreter on each target machine? If you do, you'll probably have to make sure everybody gets a standard install and write some tools to make sure there's a common setup (file locations, versions, etc). If not, you can go for an exe based distribution where each tool is shipped as an exe with an internal python intepreter and libraries).
A side aspect of this question is whether you care about isolation -- ie, if you distribute one tool on Monday and a different one on Tuesday with a few changes in your core library, do you want them to be reading off the same python files, or do you care? Isolation has pros and cons -- the brutally short version is that it's wasteful of disk space, but it tends to ensure that old stuff keeps working as it did before (which you may or may not like) exe-based distribution leans toward more isolation, although you can work around that if you have to.
<DISCLAIMER> I generally have a strong prejudice against maintaining a full pythonn install unless the target users are also programmers. Python expects a certain level of manual installation maintenance by somebody with a programmer-type personality. It's easy for people to get into trouble by trying to follow instructions off the next and suddenly having a different set of libraries than everybody else in the building . It's also possible for people to install tools off the internet that install their own pythons, and that can really screw you up if you get a different version of a particular library in 'your' install. I prefer closed distributions like exes. The only exception is for Maya users, who have an isolated install already which I don't mind leveraging since I know it's there and usually pristine
For this reason I'm not going in to the "standard" python way to distribute loose files, which is the combination of distutilsand easy_install. If I was doing IT for a lab full of NASA guys maybe. Otherwise, blecch.
2) What's your UI language? That will dictate the details of any .exe based distribution. WX or PyQT applications have their own procedures but basically you'll be compiling an exe with included dlls for the GUI and you python code as a resource. You'll need to create an installer to handle all the dependencies, which is a sad fact of life in windows land; Both WX and QT have options for doing this.
The killer here is DLL dependencies -- you'll need to make sure your users get the right version of stuff you don't even touch, like the VisualC++ redistributable that WX depends on. Make sure to do your testing on a clean machine, the DLL thing is madness inducing because (as a developer) you frequently have things that your users don't). Try using Dependency Walker when things get ugly.
A somewhat less evil alternative, if you don't need lots of specialty cPython modules, is IronPythoni. You can build a C# gui app with an IronPython interpreter and have windows native UI plus the .Net libraries to play with. The downside is that IPy is a 'reverse engineered' python -- it's not binary compatible so some modules with C cores don't work (lxml and p4Python come to mind, although they've finally started supporting ZIP files). The plus side of going with IPY is that you could deploy the apps with ClickOnce , which will handle automatically updating your users to the latest version. If you go this route you have a dependency on the .Net framework, which is a pain but it's a pretty simple install from Microsoft, it works on all windows 7 machines, and you can make your ClickOnce's install it for you.
An outside option if you want to go for web based distribution would be Jython. If you control the server, you could run some of the UI server side; otherwise you could try using the outdated Java Web Start path to give your users simple one-click download and run of tools. You'd be shipping python code zipped up into JAR files if you go this route, you would have a dependency on Java (which most people will have). You'd get the Java UI librarys ( Swing or AWT ) for free if you go this route.
3) In all cases, I'm a big fan of keeping my own code in .zip files of pyc's. One of the number one source of bugs in open installation is conflict between files; say, for example, you refactor a module into a package but don't delete the old pyc file from your original module file. You'll continue to use your old code and won't even know it until you hit a bug. Zipped PYCs make sure that the state of code you're sending out is predictable and there won't be any phantom pycs lying around . Plus they are less likely to suffer from users adding their own stuff into your sandbox.
4) If you go with source control as your distribution system, you probably want to look into having a two-stage setup. You don't want to confuse the source control you use for your own work with the one the users will be getting things from -- if every checkin you make goes right to the users you are asking for trouble. You can't control when they do their gets, so they could easily get half of a multi-part checkin and go blooey. At the very least you should have a procedure for branching or move-renaming finished scripts over from your work location to the distribution location.
Personally, I prefer to publish stuff to a distribution system and use source control for source control. A real build setup with automated tests can save you a world of headaches . I remember one company where the entire art staff was idled for three hours because somebody checked in a maxScript in Unicode, instead of ASCII -- then everybody got it via sync and everyone's max blew up, taking the auto-sync system with it so all of the changes had to be synced manually for 100+ artists.