В общем было железо, работало на меге16, с дисплеем и тд. Заставили расширить функционал, и столкнулся с тем, что флеша уже не хватает, очень много схавала графика на дисплее... Часто встречал(в тех же телефонах), что программа на микроконтроллере запускается с внешней флеш-памяти, а на самом МК есть какой-то примитивный бутлоадер. Как-то можно такое организовать на меге, что для этого нужно?

Нельзя - ATmega не умеют выполнять код из внешней памяти. Вот в телефонах - да, целый выводок аппаратов от Ericcson имел ядро AVR и умел выполнять код из внешней памяти (как из EEPROM, так и RAM, что позволяло даже загружать свой оверлей в оперативку). Увы...

Вот пожадничали..

Может быть, проще заменить mega16 на meg324 или 644 ? По ногам совместимы, по периферии снизу вверх вроде совместимы (разве что обращения к периферии подправить...)

Думаю, оптимизацией да исключением графики можно будет обойтись.. Но спасибо, как для замены - очень даже неплохо

Так грузите графику отдельно с внешней памяти.
На AT89c2051 я так и делал, стоял граф дисплей ~96x48 и все красиво работало с программным I2C.

А можно просто замутить что-то типа интерпретатора в памяти программ контроллера, и выполнять инструкции из внешней памяти...
Особо критические участки по быстродействию оставить.