What is the best version of iOS to use on an iPhone 3G?
iOS is always being optimized, and Apple's OS's are known for running faster than previous versions, even on older hardware. iOS 4.0 was bad on the 3G, but 4.1 is much better.

As a rule of thumb, you're always best running the latest version of iOS, unless you're a jailbreaker and/or unlocker, in which case you should run the latest exploitable version of iOS and the baseband.