I'd say that 6x8 is probably the minimum you'd want. (For me it is quite nice).

Also very important are things such as tilt, pressure, etc. The Wacom Intuos line, for example, has better sensitivity and X-tilt, Y-tilt and twist. They also have those handy buttons and touch-strips on the side.