Mine is not only slow: it also crashes.
I have also made the mistake of updating my iPhone 3G to iOS4. I thought I'd be finally able to use the camera to record movies, not just pictures (BTW: Apple focused on "multitask" and such, but nothing about the ability to use the camera for recording movies, so it was just a [bad] guess from me, and the "multitasking" isn't even available for 3G).
Anyway, I'm experiencing the same speed issues, but with additional hangs. The main problem I have, additionally to the slowness, is the iPod playback: when I do something else with the iPhone (e.g opening another application while the iPod is playing) the music jerks. If I do this too much (e.g playing a cards game while listening to music) the music finally stops (after jerking very much) and, sometimes, the current application (e.g the game) crashes (like a force quit). I then quit the game, launch the iPod again and see the "current" music, with the position at 0:00 and the "play arrow" (so the playback has reset) and, in "random list mode", the track has been set to the first one (1/x).
I have read the first 2 pages and the last 3 in this thread, because 19 pages is really huge. But I haven't seen anyone talking about this kind of hang, thus my reply.
BTW: anyone knows "why" this slowdown actually occurs? My guess is about the new "multitask" feature. Some have also telling Spotlight is the culprit, but I have tried disabling it and it's not better now.