Firstly, to answer your second question, definately internal. Much cheaper, and also faster.
Now to answer what size, I guess that really depends on what you intend to use it for. Do you want to store lots of large audio or video files? If so, I'd probably recommedn an 80 GB hdd or larger. Prices are pretty cheap right now. You could get a 40 GB for around $80 or an 80GB for about $110.
I'd really recommend not getting anything less than 40 GB because it really isn't gonna be any cheaper. 20 GB and 40 GB are about the smae price right now, so you'd be better off with the 40, or larger if you want.
One other thing I should add, is that you'd be better off with a 7200 RPM hdd rather than a slower 5400 RPM. The prices aren't much different, but the performance would be noticable. Also, for the love a man kind, stay far, far away from any IBM hard drive. Avoid them like the plague, which apparently they came down with. That's the reason you'll find them much cheaper than other brands right now. They have some major overheating problems and are very likely to self-destruct, sending all of your data into generation X (). Seagate and Maxtor drives are great. The WD special edition drives with 8 MB cache are good too.