If you update to iOS 4 on an iPhone 3G the performance, to but it mildly, will be poor to the point of frustration. When I first updated mine it was so bad I didn't want to use it -- though admittedly I'd gotten used to an iPhone 3GS, then iPhone 4, and it's never easy to go back.
iPhone Forums and stoovie to the rescue. Turns out there are a few things you can do to make it faster to the point of livable:
If you're still having trouble there's always the nuclear option:
Unfortunately, it's Jailbreak territory if you want to downgrade from iOS 4 to iOS 3.1.1 again, and many users seem to have problems even with that method. So try the above methods first and let us know how they work for you.
[Yeah, my iPhone 3G has a cracked screen but that's totally unrelated to the performance issue, poetry aside]