I think its case by case. Some find it faster after the upgrade. I suspect its cause by some data or apps during the upgrade. Some find it running alright after doing a clean install. Or maybe its specific to certain batches of iPhone 3G hardware we will never know. Apple is rumored to release 4.0.1 pretty soon, so hopefully it will solve this slow issue on 3G hardware. iOS 3.x code base is Leopard base. iOS 4 is Snow Leopard. So by right iOS 4 should run faster if not smoother on same hardware base on Leopard/Snow Leopard upgrade experience.
"iOS 3.x code base is Leopard base. iOS 4 is Snow Leopard"
Along with other changes, many of which do not affect the iPhone either, the biggest change in Snow Leopard was to switch all binaries and the default compilation target from IA-32 to AMD64. You shouldn't expect the Leopard -> Snow Leopard upgrade experience to translate to ARM-based mobile phones.
PS: I upgraded an iPhone 3G to iOS4, some apps are slower and others even crash more often, but the home folders and the "Cellular Data" setting in Settings->General->Network make it up for me.
My experience has been horrible. I noticed bad slowdown in every app launching immediately after the upgrade. Apps took 30 secs to 1 min to launch (twitter, lose it, even calculator).
It progressively got slower. Keyboard response ground to a halt. It would take 3-5 secs for the keyboard response to show up on screen.
It became an useless paper weight.
I tried restore to 3.1.3 a few times and I would give up at the 1015 error and restore back to 4.0, which was probably a "clean" install. It didn't fix it.
The primary feature I was interested in was the orientation lock which is not available in iPhone 3G. Threaded email is nice, but not a deal breaker, same with folders.
Lifehacker has a guide: http://lifehacker.com/5572003/how-to-downgrade-your-iphone-3...