I've noticed increased sluggishness with my 3G phone with each successive update. The update to iOS4 made things only incrementally worse than the prior update, but I do get the feeling that they are a hair worse rather than better. Note that I did a full clean wipe of the phone instead of a restore (details of that fiasco I think are higher up in this very thread).

Some things I've noticed about my 3G phone that has helped me speed it up occasionally:

- If the phone completely locks up to the point where it seems to be unusable, sometimes pulling out the SIM card, blowing on it Nintendo-style, and re-inserting it, helps. I think there's a processor thread that's constantly checking the SIM card, and if there's intermittent connectivity to the SIM, you'll get that thread locking up and causing other dependent threads to lock. This, by the way, is coincident with a related symptom: Sometimes my phone would just say "No Sim".

- There's a free app called "Scan" that will free up RAM on the phone. Running that occasionally helps. For instance if I run the app before I run the TomTom navigation app, then the user input prompts on TomTom are more responsive (though still too slow for my tastes).