There are a few ways to optimize your code and reduce the size. Have a look on this document from Atmel. I've used some tips to reduce the size of my bootloader once.
enter link description herehttp://www.atmel.com/images/doc8453.pdf
For the AVR family I'm not familiar with any option. You could use a small QFN package for the atmega328p as well... You might find some small ARM with much more memory and small size.