Aja, bien, estas asumiendo lo correcto al pensar en que tal vez el PIC18F452 no tenga memoria suficiente, de todas formas, te animo a que si quieres seguir en los pics, tal vez puedas buscar algún 18F más grande con más memoria

Me parece bien que hagas 4 matrices si no quieres complicartela por ahora con una única matriz más grande , teniendo que trabajar con el linker y con algunas opciones del compilador. De todas formas si te interesa, hay un link muy interesante en las FAQ (Preguntas Frecuentes) de Microchip) que explica como es el proceso. La verdad no he tenido tiempo aún de traducirlo pero si te interesa y entiendes el inglés he aquí el link
MPLAB C18 FAQsEn cuanto al uso de una memoria EEPROM externa no son difíciles de usar pero todo depende de cuanto tiempo dispongas para codificar la comunicación

. Básicamente las hay i2c y spi. Personalmente creo que las SPI son más simples de controlar, asi que si consigues una de este tipo, bienvenido sea.
Si los datos cambiarán con mucha frecuencia, debes pensar en que tal vez una eeprom no sea lo mejor. Hay unas memorias
ferro magnéticas que podrian ser justo lo que necesitas, son como eeprom pero se graban muy rápido.
También hay memorias ram estáticas y si no necesitas persistencia al apagar el micro te servirían. El tema es que suelen ser paralelas y por lo general son caras aunque yo he averiguado por bastante RAM, 32 MegaBytes o similar. Supongo que por poca memoria tal vez también hay, sería cuestión de buscar