What file format should I use to format my new external HDD?
FAT32 works on every system, but files cannot be larger than 4GB in size.

There is exFAT, which works with larger files, but it isn't natively supported by Linux. You can however see this link how to get it working on Ubuntu for example (read and write support with this solution).