The main problems you will have with an FPGA:
- It is hard to find parts with 5V supply or even 5V-tolerant I/Os. You can't easily use a 3.3V part.
- An FPGA is volatile (like RAM), so it needs something to load code on it. Some FPGAs have a bootstrap system and they can load code from an external serial ROM.
FPGA is not "magic chip that can replace everything".
You will have better chances with fitting the gate array implementation in a CPLD (which is more like EEPROM), if you can find one large enough to fit everything.
You will also have hard time tring to solder your replacement FPGA board to the 100 fine pitch footprint on the PCB. Not impossible, but a lot of trouble ahead.
Regarding CPLD, you will have to go for the biggest. The GA does not fit a XC95144XL as it require 166DFF/Latch + glue.
It would fit the XC95288XL which is the large CPLD xilinx offer with 5V tolerant IO.
BTW, CPLD (at least xilinx ones) also need to be initialized at power up, but the configuration is stored internally and init done automatically. Bigger is the PLD, longer is the init phase.