isoToxin gave this advice and it worked great for my iPhone. It is really fast now.
post from isoToxin :
Despite being hesitant, I upgraded my 3G last night, and I'm very surprised at the performance because it's actually a bit faster than 3.1.3 was. :o I'm wondering though whether a lot of the reported issues with performance on the 3G come from doing an "update" in itunes rather than a "restore". As I understand, and update will simply try and "work around" your existing data on the phone and fit IOS4 in where it can. A restore will format the entire phone, and install IOS4 fresh. I installed IOS4 by choosing the "restore" option in itunes, and of course after this was finished I was left with a completely blank phone. Once that was done (only took about half an hour), I proceeded to hook up to itunes and restore from my backup. I then synched my apps (which took a while, about an hour), and now I'm gradually filling it with music/films again. I'm really pleased with IOS4 so far, the speed of certain things (like the menu transitions, and the browser) has definitely improved on my device. There are the odd moments where the phone will pause for a few seconds, but I had this frequently on 3.1.3 and it's certainly no worse (as I was lead to believe it would be). I'd recommend to anyone having issues to
1. Take a full phone backup
2. Choose "restore" in itunes.
3. Restore from backup afterwards.
Worked great for me.