I've done some quick experimentation with py2app and packages installed as eggs (stopping short of monkeying with py2app itself).
As it currently stands, py2app's dependency finder misses the dependencies of modules within eggs. I was easily able to get my setup script to copy the eggs I needed into the app's site-packages and generate a .pth file to use the eggs, but found that the app wouldn't run because of standard library modules that hadn't been included.
In some respects, eggsploding the egg's packages into a directory and letting py2app pick the modules up from there is beneficial, because that would probably include just a subset of the egg in the final app. A smaller final app is a good thing. py2app also includes just the .pyc files this way, whereas the eggs I have include the source.
I haven't tried py2exe yet, but I will probably end up with a similar approach.