so this HDD must be readable by both, Apple and Windows.
When you say Windows doesn't support Apple file systems, does that mean you can't dump a file created on the mac (say a home movie clip) onto the PC for whatever reason?
Don't mix file formats with file systems on storage devices.
It means, from a Windows PC, you can't copy files onto a HDD that has been formatted on a Mac with Apple's HFS file system. And you can not copy files from a Mac onto a HDD that has been formatted on a Windows PC with NTFS.
And the other problem is most archived movie files are around 4 GiB +/- right?
But there is a workround:
Format the HDD on the system you prefer. Then share it over your local network (wired network is highly recommended here). That way, you can circumvent the file system restrictions.
And IIRC, its either ATV or the Apple Airport that doesn't recognize FAT32 drives, or am I confusing the issue?
No idea, I am not familiar with Apple stuff.
Then there's HFS+... would it not be better to format the external HDD this way than with a windows format?
You can do that, but Windows can't deal with that HDD then, unless you have 3rd party software for HFS support installed.
Edit: There are also 3rd party NTFS drivers for Mac available: http://www.tuxera.com/products/tuxera-ntfs-for-mac/
Edit2: Never versions of MacOSX seem to have a read-only NTFS driver aboard.