I was in the same boat, and ended up wiping my 3. That helped more than it should have, especially for the pain in the ass that it was to reinstall the stuff I use regularly.
Wiping it actually increased responsiveness? I guess I'll give that a try.
Working theory is that it cleared out things like Safari's caches (which I could have done without a wipe, of course), and cleared up free space. iOS isn't a happy camper when it lacks free space.