Downgraded my work phone to iPhone OS 3.1.3. YESSSS. It's actually a usable device again!
Apple should have never allowed 3G users to upgrade to iOS 4. About the only real feature that we get are folders and a truckload of slowdowns and app crashes due to the different memory layout (which 3GS and 4 owners do not generally get, probably because those devices have more memory). It literally took upwards of 5 seconds just to go to the home screen. F'in ridiculous.
But anyway, if any other 3G users were dumb enough to upgrade, this guide on Lifehacker is detailed and easy to follow:
http://lifehacker.com/5572003/how-to-downgrade-your-iphone-3g%5Bs%5D-from-ios-4-to-ios-313. Of course, I had numerous issues following it because I used my PowerMac for everything, and nobody builds any software for OS X 10.4 and PowerPC anymore, so naturally I had to jump through a bunch of hoops to build iRecovery, but it was totally worth the pain and suffering.