Is your 3GS on iOS 4.2.1? If its not Jailbroken, definately get this version as its excellent!
Also, what I recommend to do to make the 3GS zappy is the following:
* Clear the cache in Settings, Safari
* Go to the multitasking bar and close down all the apps (double clicking the home button twice)
* Do a hard reset (holding the home button and on/off button together for a few seconds until the phone switches off, let go of the buttons when the Apple logo re-appears)
I am confident this will help as my 3GS is so quick that I have even compared its speed to 2 of my friend's iPhone 4's, both times I found mine was quicked in opening and closing Apps, Messages, etc....
Try it, you have nothing to lose 🙂