It offers very fast in-place decompression and is available for several platforms other than Linux, including ARM, MIPS, PowerPC, DOS and Win32.
For Win32 platforms, there is a GUI version (download here), but it uses an older version of UPX as its base which should not be a problem if all you are only compressing Win32 binaries.
The command line version works on all supported executable formats in all OS versions.
If you just need to compress non-executable files, 7-Zip is a file archiver with the high compression ratio. The program only supports the 7z, ZIP, GZIP, BZIP2 and TAR for packing, but unpacks all of those plus ARJ, CAB, CHM, CPIO, DEB, DMG, HFS, ISO, LZH, LZMA, MSI, NSIS, RAR, RPM, UDF, WIM, XAR and Z. Most of the source code is under the GNU LGPL license; there are restrictions on the unRAR code portion.
Of interest to Linux users is the abilty to uncompress CAB and MSI files to make it easier to use the files in the archive with WINE.
7zip began as a Win32 application, but it was so useful that it has been ported, as p7zip, to Linux, Amiga, BeOS and Solaris. There are packages in Debian unstable and Mandriva.