So what's the maximal number of code lines? Just an estimate. 100, 200, 500?
I'd guess at somewhere about 1000 to 2000 lines of code.
The demo16x24 LED matrix program I posted a while ago is about 450 lines of code (actual CODE lines, as counted by one of those "metric" programs; it's 700+ lines of program), and compiles to about 5500 bytes of object code.
The AF_WAVE library for Adafruit's sound playback shield almost fills the 168, IIRC, and has about 1400 lines of code (not including the .h files.)
As others have mentioned, the 1K of RAM is frequently a problem long before you run out of code space.
You can potentially put an interpreter and SD card file system code in the program memory, and connect up a 2Gbyte SD flash card to contain programs to be interpreted, but that's probably cheating, right?