Duemilanove: simpler, cheaper, better support
Mega: near guarantee on enough memory and program space, PLENTY of pins
The choice is yours, I'm currently using a duemilanove for my project...
It needs to operate 6 servo's, two serial devices (one through a software serial), an LCD shield and at least a single light sensor.
That combined uses up a total of 20 pins, the duemilanove has.. 20.
Now I have a multiplexer in the system so I can expand my sensor equipment, but still, its cramped!
If you feel you'll have more stuff connected to it, go for the mega, if not, the duemilanove will suffice.