I and friends of mine made some good experiences with the tablets from Wacom.
The Bamboo series contains different tablets in different pricing categories.
My Bamboo for example is connected via USB, the pen as 2 Buttons, the tablet is only sensitive to the pen, has some more buttons and works with my linux out of the box.
So this should satisfy your needs.
Wacom supports Windows, Mac OS X and Linux without any problems as far as I know.
They link to the Linux Wacom Project on their official homepage for driver support.
After a little configuration of the input devices it works pressure sensitive with Gimp.
For advanced configuration of all tablet buttons and touch sensitive areas theres the Wacom ExpressKeys project, which also works fine under the different distributions.
To your questions:
What are good sizes of such tablets in
This totally depends on your usage of the tablet. Are you just using it as an addition to your mouse? Are you gonna start some kind of digital painting? etc.
A common size for the "drawing" area of those tablets is ~ 5.8" x 3.6". This should work fine for the average usage.
More important than the size is IMHO the resolution and pressure levels the tablet supports, because this will influent your work. Keep this in your mind when you are comparing tablets.
Is there is some good guide how to
setup it under Linux/X?
The Linux Wacom Project maintains a nice Howto to that topic.
Also there are several guides based more ore less on the used distribution, e.g. ARCH and Ubuntu.
What are other great programs that are
really easier to use with a tablet?
I often use my tablet also for audio processing. The editing of different audio tracks with a pen feels much more natural for me.