When buying a HDD there are a couple things you should watch out for.... DONT BUY HITATCHI! Hitatchi drives have a history of burning out after about 3 months.
As blizz said the rpms will speed up your load times but not your running speed (unless your loading constantly) also solid state drives are the best for that kind of thing (no moving parts = fastest) but they are also the most expensive.
As far as the lower gig drives, i wouldn't reccomend it. The thing is, when you have a bigger hard drive, you tend to use it, when you have a smaller hard drive, as long as its not way too small, you make due, so once you have the 1 TerraByte... you will find a way to use it.
Also, because you are going external, you have to remember to be careful that you dont drop it, and keep in mind that the rpm speed will only help to a certain point because your USB port can only transfer data at certain speeds.
If you really want your comp to run fast, have as few programs on your main HDD as possible. It will make it so that your main hard drive can concentrate on running windows. Windows needs a certain ammount of free space to survive to begin with.
Another thing as far as speed goes is that when you start up your computer, almost any program you have installed will want to have their "quick loader" in your running programs. This means aditional time on start up to bring up these background processes which eat up ram. There are a few programs that can help prevent/stop this, but most of them cost money. A good thing to do is just download Spybot Search and Destroy and go into the advanced options where you can set what processes it allows to start up on start up. This will increase your boot speed and the ammount of free ram you have at any given moment.
Another quick fix is to reformat your hardrive, this will get rid of fragmented files, or rather unfragment them. What happens is... you know what, screw it, im just gonna start a new topic on good computer higene, you can read up on it there.
My end all sugestion is get a external hardrive that has around 300-500 gigs. Anything more is too expensive, and anything less is a waste.
I personally recomend:
This oneThat website is great too, i have yet to catch them giving me the shit end of the stick, and most of the time they are actually cheaper than retail stores. Not sure if they ship outside the USA though.
That particular harddrive is roughly 137.4 aussi dollar (conversion rate is 1usd=1.527 Aussi)