Regarding configuration memory, could you have the arduino read out from a serial flash? They're pretty easy to bit bang or control over SPI, and you can get a 64Mb pretty easily.
I do prefer the idea of using EEPROM if I was going down that route, though, so it'd be more like a CPLD than an FPGA. I just need a good way to load the only bit of remaining discrete state - the output enables - on startup. My best idea thus far is to dedicate half the EEPROM to configuration data, store the latch states at address 0, and use two RC networks to create rising edges first on a register latch pin then on the highest address pin to latch in the config before enabling the EEPROM in 'operating mode'.