Since you will not be able to find any PIC with more than 1k data EEPROM,
I would suggest you to go with an external 32k 24LC32 EEPROM. This need only two wire, one for clock (SCL pin) and one for data (SDA pin). Can go as fast as 400khz and it's very easy to set up an program with PBP. This left you with plenty of pins availables for the LCD.


J-P