I really hope iOS 4.1 improves the experience on the 3G device. It’s *terrible* with iOS 4. Buggy and painfully slow.
This video seems to be about right: “OS 4.0 on 3G iPhone (parody)“.
[Update Jul 30 2010]
I tried this tip “Disable Spotlight Searches to Improve iPhone 3G Performance on iOS 4” combined with the “double hard reset“… Not sure that it helped yet. Opening the Messages/SMS app still takes ~5 seconds, but some actions feel a little better. (Related note, I do the same, disable as much Spotlight as possible, on all my desktop machines as well, for the same reason — the daemon is a painful hit to performance for a feature I don’t use.)