You can have UPX and autoupdate (in theory at least).

http://xdelta.org works and has the newest version. http://www.xdelta.org does not work for some reason. The link you provided has a dated version. I've updated the link in the OP.

And yes, this is for people who don't have much free space on their flash drives so that they can use UPX without having to download a full update or carry a full backup (which defeats the purpose).

You're not allowed to. That's why I'm working on a batch file instead of suggesting that you add this to the launcher or something like that. It's for end users who wish to UPX the binaries and be able to autoupdate on-the-spot without backups.

I feel silly now. After much trial, error, and frustration, I finally got it to work.
Anyway, the batch files can be found here:
http://www.digital-signal.net/bahamut/batch/UPXAU/testing

Instructions:

• Usage: [batch file] [file to prepare]
• I will add echo messages in a later release.
• As I stated before, only one file can be processed at a time.
• I do not have error-catching mechanisms implemented yet. You may seriously screw something up, especially if you do not follow directions. I make no guarantee that this will work or that it won't do anything bad.
• I try to give as much information as possible for debugging/troubleshooting. If there is something you think I can add to further this, let me know.
• You will need UPX, Jacksum, Java, xdelta, and cp[1][2].
  cp, Jacksum, and Java are not strictly necessary; cp is needed for preparexdelta.bat (I can't figure out how to do it with copy or xcopy), and Jacksum (which depends on Java) is used to verify that everything is done correctly.
• You must replace %rootdir% with the location of the programs (UPX/Jacksum/xdelta/cp).
• You must cd to FirefoxPortable\App\firefox (this applies to all batch files.
• The files in FirefoxPortable\App\firefox are modified; the files in the temp directory are not.
• Since these are not ready for the regular joe, and is out for testing purposes mostly, the backup files made are not deleted. I strongly discourage using these batch files on a flash drive (copy FxP to a hard drive).
• cp seems to give the backed up files the read-only flag.
• You must use the original file as the argument. Remember to remove the read-only flag if you have to replace the modified file in FirefoxPortable\App\firefox.
• You can change the options used by UPX and Jacksum, however, make sure that the changes are applied throughout the entire batch file (e.g. don't compare a sha256 sum to a sha1, don't use --best --all-methods the first time and -9 --all-filters the next)
• xdelta does not tell you if the patch was applied correctly, but only if it could apply a patch.

File-specific:

• preparexdelta.bat creates the temporary directories and copies the binary files to those directories. It doesn't accept any arguments.
• xdeltatest.bat verifies that the whole process will indeed work. If the first checksum matches the last checksum, you should be good to go. If not, check that your directories are correct, that every program ran and did what it was supposed to do, and that the method/level/filter used by UPX are the same both times.
• doxdelta.bat packs the files and creates the patch files. Patches are stored in FirefoxPortable\bak
• prepareupdate.bat unpacks the files and restores them to the originals so that autoupdate can use a small update patch. The originals are re created in FirefoxPortable\likenew.

[Moderator RM: Fixed your link :)]