You can use pretty much any size drive you like but it's the version of the OS that dictates how you'll be able to actually use it. Anything before OS 7 is limited to using partitions of up to 2Gb (i.e. the drive would need to be partitioned into 2Gb chunks) and OS 7 to 7.5.1 is limited to 4Gb partitions. OS 7.5.2 and beyond raised the partition size to 2Tb (and if you get a drive that needs partitioning into 2Tb chunks then I'm sure we'd love to see the pics ). In your case you should be able to use 4Gb partitions with no problems (I have an 18Gb external drive split into 4Gb partitions and it works just fine)

As to formatting it then Apple's Disk Setup is usually good enough to get started with (it'll partition if you need it to) but some versions can be picky about which drives they'll deal with (I can't remember which versions are 'awkward' and which aren't but someone here'll know and be able to point you in the direction of a 'non-awkward' version).

As to getting a drive then it depends on how much you want to pay, whether the drive needs to be brand new, how much hassle you want to go through etc. Here in the UK external SCSI drives are becoming more and more difficult to get hold of. Ebay can be useful or you could always post a topic in the Trading Post section