Go with a '1284 based board, 16K of memory.
I am selling bare boards (assembly required) that are comparable to duemilanove but are populated with a '1284 instead.
See Reply #282, page 19, in this thread
http://arduino.cc/forum/index.php/topic,80483.270.html
and Reply #287, page 20
http://arduino.cc/forum/index.php/topic,80483.285.html
$4.50 a card to US locations; international, need to check where its going.
Reply #224 on page 15 for schematic & pics of bare board
http://arduino.cc/forum/index.php/topic,80483.210.html