Speed comparison of iPhone 3g with iOS4 and iOS3?
Yes, it does slow down. It's more and more noticeable as time goes by. 
Apple has acknowledged this issue and they are looking into it.

Here are tips to make it run smoother again. (This is just a solution that has worked for many people. This is not Apple's official solution. They are working on a solution.)

1 - Disable spotlight search. 

Settings -> General -> Home Button -> Spotlight Search. Uncheck things you don't search for. Uncheck all is best I guess?

2 - Perform DHR (double hard reset)

To perform a Hard Reset, press and hold the Home and Sleep/Wake buttons on your iPhone simultaneously for 5 to 10 seconds. After a few seconds the Slide to Power Off notice will appear, ignore this and keep holding down both buttons. In another few seconds the device should abruptly turn off, followed by the Apple logo and a reboot. Now release the buttons. 

If your iPhone remains powered off, wait about 15 seconds then boot the phone by pressing the Sleep/Wake button. 

Do this one more time.



I think this is related to iPhone running out of memory (RAM). But that's just my guess.