Using a spare laptop, I used GParted to remove the 16gb partition. Then hit Apply. Once done, I had GParted make a 4096MB FAT16 partition and hit apply. I did them as 2 separate steps to be extra safe.
I then inserted the Eye-Fi into my PC and the Eye-Fi Center software saw the Eye-Fi card, so that was a success.
I installed CHDK to the card. Used CHDK to make the card bootable. Installed the Ultimate Intervalometer script, and locked the card. Inserted Eye-Fi into my camera and turned it on, it booted to CHDK. Configured the Ultimate Intervalometer script and sure enough my FTP site started receiving files.
So far so good!

Time to let it run for a few days and see if anything glitches out.
Any other tips I should know about?