If you have an Express card port, and don't mind a little extra expense, it's worth running eSATA for performance reasons. Firewire 800 is also a good option (though more than 3 times slower than eSATA). Firewire 400 is a bit sketchy for intense usage, and don't even think about USB; there's no DMA support, so transferring from the hard disk to RAM has to be done by the CPU (at the expense of many CPU cycles).
On the downside, eSATA does not yet provide power (you'll need a power supply for the external hard drive) and since most laptops do not have eSATA connections it'll require an ExpressCard port. The ExpressCards themselves are pretty cheap; you should be able to get one for under $40.