Right now, I'm making a project involving a ks0108 display where saving up is really important. Since I wanted to use a 328, and still use some pins, I've set up an ATMEGA8 (7.somthing Kb of free space) on a breadboard, and uploaded to it a simple code with the library and a serial communicacion protocol, to interface with the Duemilanove (the one that makes all the calculus and reads the sensors).
It works great, at this very moment I'm looking at it, and it's displaying a real-time sinus wave generated by the own ATMEGA8, so so far it doesn't seem to be too slow.
Salu2