It seemed that after every Apple firmware upgrade, my phone became more laggy and unresponsive.
I tried all sorts of fixes - disable Push and Notifications, removing all the music and videos - all to no avail.
Clicking sleep/wake would take 8 seconds for the phone to respond, and I could type 10 characters on the keyboard before anything would appear.
However, I found the solution to be something quite simple - so I've posted the information here so Google can find it and hopefully help someone else!
How I fixed my iPhone
For the technically minded, there is more information below. For those who like to skip to the chase - you must make Safari unload itself when you close it.
Because Safari is an Apple application, it doesn't unload from memory when you close it. This means there is very little free memory for other programs to use which makes everything run more slowly. To make Safari actually unload itself, follow these steps:
1. Tap the Pages button in the bottom right of the screen.
2. Tap the red 'X' to close all open pages.
3. When all that is left is a blank page with no X, tap Done.
4. Now, close Safari by pressing the Home button.
With no page loaded in, Safari unloads itself from memory instead of hiding itself. Annoyingly, you have to remember to do this every time you've finished using Safari.
My phone still has Push, Notifications and MMS turned on with no apparent problems (although turning these off seems to help other people).
When my iPhone 3G with iOS 4 first starts up, it has about 32Mb free memory and 10Mb 'inactive' (Inactive memory is a cache of recently used information, that the iPhone will discard if it needs the room). If I run and then close Safari, I end up with 12Mb free memory, 15Mb inactive and 17Mb "unaccounted for". As most apps will need more than 12Mb, the iPhone has to start juggling with its memory, slowing everything down.
You can verify this for yourself by installing a free memory monitoring app such as "Memory Sweep". Run the memory app after using Safari and see the results.
Note; I have no association with this particular app - there are plenty to choose from.
Another speed tip - disable Spotlight search
I don't use the Spotlight search - the "leftmost" page on the home screen. As this is continually indexing the phone's data (including all Notes, Mail and Messages) I would assume it uses some of the phone's resources.
A new setting in iOS 4 lets you disable this. Go to Settings - General - Home Button - Spotlight Search, then untick all of the items (or at least, untick all the ones you don't want).
Yet another speed tip - disable MMS (Multimedia Messaging)
This tip was widely reported with previous firmware updates, and you may find it useful still.
If you don't send or receive multimedia text messages, turn off the feature by going to Settings - Messages - MMS Messaging and setting it to OFF.