Yep, the 3G is a sloth with iOS 4. I need to downgrade mine, I gave it to my dad - I doubt he notices the lag. The new iPhone 4, OTOH, is pretty snappy. IMO, it's what the first iPhone should have been. After playing with my original and then 3G iPhone quite a bit, I got into the habit of saving all the old OS restore images that iTunes downloads. I still have my iPhone OS 1.0 restore image
ETA - I just did it. 11 minutes start to finish. Make sure you have the 3.1.3 restore image (file name is iPhone1,2_3.1.3_7E18_Restore.ipsw) and RecBoot(forces the iPhone to exit the restore mode, since the 4.0 to 3.1.3 downgrade won't finish properly in iTunes - download link at the page that MALT0SE linked to above). Hold down the option key while clicking Restore to be able to select the proper restore image, when it's done it will give you an error and tell you it needs to be restored again. Don't do that, instead launch RecStore Exit and click the button. After that I had to unplug the iPhone and plug it back in, then it re-activates the phone, and if you have a pre-4.0 backup you can restore from that, otherwise you need to set it up as a new iPhone(4.0 backups won't restore to a 3.x phone). And boom, back up and running with 3.1.3 on the 3G!