Which connection interface should I use with my next external HDD?
If you simply want speed, then FW800 is faster than USB2 (you do not have USB3).

USB has drawbacks which result in a lower then promised sustained speed (FW800>FW400>USB2).

Edit: I've done some research to get real world numbers. While the theoretical speeds are (100MB/s vs 50 MB/s vs 60MB/s) the real world results result are (90MB/s vs 30MB/s vs 30MB/s) due to limits cause by bridge-chips (german source). Since hard drives allow transfer speeds above 30MB/s, you should take FW800.

If you want to be upgrade safe for a future Mac, I'd take USB2/3. Firewire support is probably going to be dropped in the near future (see Macbook Air).

Thunderbolt is overkill - as you said.