I have an iPhone 4 too, 32GB model.
1) The new iOS's which have been released, maybe they use more overhead.
This is clearly a factor. Mine isn't as responsive as I remember it being when I just got it, but I also have to remind myself that this was a rocket with gorillas strapped on compared to the iPhone 3G I was used to. Interestingly mine's home button stopped working from all the running in the rain (I use Runkeeper) during the winter, so I took it in to the Apple store, and they offered me a refurbished one for ÂŁ130 or so, which I took.
The performance didn't change at all, but they did tell me that something was messed up in my profile, which is causing it to be sluggish and apps to crash (a problem I was having). They suggested I set the phone up as a new device, and not restore my backup to it. I followed this advice [1] and it sure did make a difference. I can't complain about the phone's responsiveness. Just to test this, I restored from my old backup, and it was instantly sluggish. Wiped the phone, set it up as a new device, and I was back to responsiveness.
[1] Small caveat: Everything on my phone is syncable via internet - mail, notes, and all the apps I use. But SMS messages isn't. It took me a while but I figured out how to get them out of my old profile and into the new, but I managed that, and all is good now.
2) The new Apps built for the new iOS's or faster iPhones.
This is probably it. The facebook application, for instance suck donkey balls. It takes about 9 seconds of showing a blank white screen before the app starts drawing. Once it gets drawing, it takes forever to download images, conversations, etc, even on wifi with a really fast internet connection (100mbit Tier 1). It's not much better on my Galaxy S2 either, for what it's worth.
One app I loved was Camera Awesome from Smugmug. It worked great on the iPhone 4, but after an update (to Camera Awesome) in December, it got really slow. It takes 6 or so seconds to start up, several more to lock focus, and the shutter lag makes it impractical. I wrote to them, and they responded that the app was only released for the first time when the iPhone 4S was already around, and was never designed with the iPhone 4 in mind. Too bad.
Another app I find incredibly sluggish lately is Google Chrome. So much so that I'm back to using Safari. The Podcast app is pretty sluggish too.
For my part I'm holding out until the next announcement. I'm hoping for a 128GB iPhone 5S
