I found this hint on Daring Fireball, and my iPhone is happy again!

If you’ve found your iPhone 3G to be almost unusable since upgrading to iOS 4, then try doing a DFU restore, as described at http://www.iclarified.com/entry/index.php?enid=1034

I did it last night, and so far the phone is loads better. It restores all your data and settings, but does a completely clean install of the firmware.

Since doing it, I’ve been switching between apps, loading websites etc and nothing has crashed (yet). Even apps that always crashed are working now!

Update: Shortly after this, I jailbroke my phone. The extra features were great – particularly having a wi-fi hotspot for my iPad, and being able to pull down a little system panel any time, to enable/disable radios or check the status of my memory/network etc.

However, performance again deteriorated until the phone was pretty much unusable again 🙁

I’ve done another DFU restore to the latest firmware… Let’s see if the phone maintains its usability this time.