Hi,
I'm using the SST25 series of SPI memory devices, technically it's FLASH and not EEPROM but I don't think it matters. A 512kBit (64kByte) device costs around 60 cents. Since it's SPI you can use SHIFTOUT/SHIFTIN or you can use the MSSP module of the '877 for increased performance. These are not 5V devices though.

I'm sure though that "any" device will work just fine.