Definitely do this, unless you have an extremely critical must-have application that requires iOS 4.

The perf "gains" from going back to 3.1.3 make the phone non-irritating again.

I don't believe you can downgrade to 3.1.3 any more. When you restore an OS image, iTunes checks whether it is a valid image with Apple's servers. After a major version has been out for a while, Apple stop approving installs of older versions.

I might go the jailbreak route if it enables me to do that.

Wow, thank you for the suggestion! I'll definitely be trying it. I can survive with webapp Twitter until my next upgrade (or even next year for the new iPhone if it's bearable enough).