Wacom http://www.wacom.com make good tablets. I have an older A6 sized Graphire (I think) which works fine with both Photoshop Elements and Gimp. I wouldn’t worry too much about the size of the tablet except maybe to get one that’s the same aspect ratio as your monitor.
Wacom tablets are great – I’ve been using one since Photoshop7 – which seems aeons ago!
I would suggest the A6 or A5 size because you can make your changes with a minimum of movement. As I understand from an artist friend, the larger sizes like A4 are mostly used by illustrators.