"The size of an egg?" surely you don't want to check on the hen and her brood.

I would consider the use of a 24C512 EEPROM to get 64kB of storage and use RS232 for interface to the PC. If that is not enough, a removable micro SD card will definitely be a good bet. However, if you think FAT12 / FAT16 for the SD card, I am sure it will not fit into a small PIC. You may have to go with an 18F series with at least 8K flash(it's just a hunch, I have no experience with FAT on PIC) A proprietary file handling on the SD card, on the other hand, will allow you to work with it on your PIC in SPI mode.