Wacom all the way.
Get a 6x8, not too small but not too big. If your just starting out, don't go blow all of your money on a Wacom Intuos, just start off with a Wacom Graphire which is pretty good value for money in terms of what it can do - then upgrade later if need be. Remember you can always sell it somehow.
Most of all it depends on what you will be doing with it - if you're doing mainly photoshop work and need pressure sensitivity, well maybe spend the big extra and get the Intuos, but still the graphire will do the work. If you're doing vector work say in illustrator, any old tablet will do pratically - vector work doesn't really rely on pressure sensitivity.
Basically the sizes are just what you prefer. As an analogy to relate to, if you enjoy using your shoulder/arm in a large swooping-manner when drawing on paper; perhaps get a bigger size tablet. Though if you just like using just your lower arm and hand/wrist, just get a 6x8. It can be handy having a big size tablet, but remember they all map 1:1 on the tablet to the computer's screen. So it's like having a screen that you draw on which is your tablet and your monitor.
Anyway, hope this helps.