I've been experiencing some performance problems as well with my iPhone 3G after upgrading to iOS 4 at the end of last week. Restarting the phone seems to help a little bit, but I'm not convinced it helps--if it does, the sluggishness certainly comes back over time.
I seem to remember similar performance problems when iPhone OS 3 came out last summer that improved with the the update to 3.0.1. Anyone else remember this being the case? or am I imagining things.
Before iOS 4 was available for download, I was planning to get an iPhone 4 later in the summer so I guess these performance woes will be over then, but I'm holding out some hope that the situation for my iPhone 3G will improve when 4.0.1 (or whatever) comes out.