Be able to use dynamic sizing

VDI, VMDK, and VHD all support dynamically allocated sizing. VMDK has an additional capability of splitting the storage file into files less than 2 GB each, which is useful if your file system has a small file size limit.

Be able to have snapshots

All four formats support snapshots on VirtualBox.

Be able to move my virtual machine to another OS or even another free virtualization solution with minimal effort (probably something that would run fine on Ubuntu).

VDI is the native format of VirtualBox. I didn’t search for any other software that supports this format.

VMDK is developed by and for VMWare, but Sun xVM, QEMU, VirtualBox, SUSE Studio, and .NET DiscUtils also support it. (This format might be the most apt for you because you want virtualization software that would run fine on Ubuntu.)

VHD is the native format of Microsoft Virtual PC. This is a format that is popular with Microsoft products.

Performance

The format should not affect performance, or at least, performance impacts are negligible.

The factors that influence performance are:

Your physical device limitations (much more noticeable on a hard disk drive than a solid-state drive… Why?)
expanding a dynamically allocated virtual disk drive (write operations are slower as the virtual disk expands, but once it’s large enough, expanding should happen less)
virtualization technology (hardware vs. software; hardware virtualization helps VirtualBox and improves the speed of virtual operating systems)
the fact that you are running a virtual operating system. Performance is always slower than running an operating system on the host because of the virtualization process.

VMDK seems to offer the panacea I’ve been searching for in terms of incremental backups: I no longer have to back up an enormous, monolithinc VDI for a single bit change in the guest.

VDI, is the native format of VirtualBox;
VMDK (VMWare format) will increase compatibility with other virtual machine software.

VirtualBox will run fine on Ubuntu, so if the goal is Windows/Ubuntu interoperability, VDI would be a perfectly valid choice.

Both formats will fulfill your requirements.
As for the other two, VHD is a Microsoft-developed format, and HDD is an Apple-developed format; these are both proprietarily-licensed, so limit cross-platform support; I wouldn’t recommend them.

However a more universal option might be to use the VirtualBox File/Export function to create an “Open Virtualization Appliance” .ova file that can then be imported into VMware. With that approach, you can port to any virtualization system that supports .ova without caring what disk image format you use in VirtualBox.

If you need to export from the same VM at regular intervals, e.g. every day, that could be a pain. But if you only move to a different technology occasionally, it should be fine.

If you have a .vdi file already, You can test whether this works without having to create a new virtual machine. Export it to a .ova, then try importing with vmware.