Im µC hast du drei Speicherarten.
1. den Flash. Dort wird das Programm abgelegt. Der Mega8 hat 8kb davon.
2. EEPROM. Die Funktion scheint dir ja bekannt zu sein. Aber ichkenne keinen AVR der 16k davon hat. Also musst du das schon extern machen. Der M8 hätte 0,5k
3. SRAM. Wie beim PC der RAM. Beim M8 1kb.

Das LCD kann im 4bit-Modus betrieben werden. Dann werden nur 6 Leitungen benötigt. Aber dann wird ein M8 schon knapp. Der Mega16 hätte ein paar I/Os mehr.

Wie gesagt, mit C habe ich nichts am Hut. Da kann ich dir leider nicht viel empfehlen. Außer du schaust mal hier im Forum. https://www.roboternetz.de/phpBB2/viewforum.php?f=34