Hi,
Currently the VLC .dmg files are compressed using zlib (UDIF) compression. If you were to switch to using bzip2 compression (UDBZ) you'd save about 20% of your download size.
For example, vlc-0.9.9a-intel.dmg in UDIF is 20374916 bytes. vlc-0.9.9a-intel-udbz.dmg in UDBZ is 17025367 bytes. That's about 82% of the total size. This is about the same percent for the 1.0.0rc2 release.
`hdiutil convert <file-in> -format UDBZ -o <file-out>` (instead of the UDIF you're probably currently using) would achieve this, in whatever step the .dmg is created in. The downside is that this errors in 10.3 and previous (instead of letting them find an unsupported .app, as UDBZ was added in 10.4), but these days I don't imagine it's a problem much.
On a side note: you might want to consider using Sparkle for updates; automatic install is a great way to force users to keep up to date. Personally, I find myself always turning off VLC's update check because by and large it's useless: downloading is great, but installing is key.