Have you considered using an SD card?
You can run them in SPI mode which means most microcontrollers have built in hardware to interface and only uses 3 pins.
http://en.wikipedia.org/wiki/Secure_Digital#Technical_detailshttp://www.circlemud.org/jelson/sdcard/SDCardStandardv1.9.pdfhttp://www.dtt8.com/images/micro-sd%20specification.pdfhttps://www.sparkfun.com/datasheets/Prototyping/microSD_Spec.pdfThe hardest part of working with SD cards is the implementing something that can deal with the FAT file-system.
I have done this for just reading files, but used a lot of program memory (it could probably be implemented better than what I did).
The other option which I have had great success with is writing raw data at known addresses on the SD card, bypassing file-systems all together; just hard-code the address in your program or you could implement a lookup table at that start of the card just to add a little flexibility. The problem is, it isn't really possible for an end user to do anything with the SD card; windows will just ask if you want to format it.
I would highly recommend HxD (
http://mh-nexus.de/en/hxd/) it allows you to open the raw physical drive and then copy and past raw data into any location you want, very powerfull. You will probably want to convert the data (icons, fonts, text, sounds...) into a format easiest to read using a simple custom program on the PC, no reason to implement common formats if you don't need to.
I have dumped raw video and audio onto and SD card and had a microcontroller simply dump the data from the card to an LCD screen and a PWM to produce video and audio, nothing to amazing, but it looked cool.