Unfortunately while booting iOS 4 GM non-jailbroken on my iPhone 3GS I found the new OS to be much more sluggish than iPhone OS 3.x, but I'm sure others who have tried beta versions of iPhone OS 4.0 felt that The 3GS sometimes struggles with iOS 4.
First of all, the lag is felt when navigating through the menus, I know that because of the animations, everything seems so fluent at first, but as you use the phone, you will notice a difficulty in opening the menus and if you somehow have several applications open in the background, then the situation it gets a bit complicated and the system starts to move more and more difficult. To be honest, this experience is similar to installing iPhone OS 3.0 on the old 3G, you could see/still see with the naked eye that the 3G is nowhere near as fast as the 3GS in OS 3.0 and the situation will be like this year when the iPhone 4 will be much faster than the iPhone 3GS. However, this speed will be relative because the iPhone 4 could still have 256MB of RAM and this hardware inconvenience could have its say in terms of the speed of the iPhone 4, especially when you get to edit a movie, play HD quality video, etc. .
I, for one, was sure that Apple would find a method to slow down the iPhone 3GS, and for me the premonition came true, the iPhone 3GS moves with difficulty on iOS 4.0 GM and the situation will not change when the final version appears, but for Apple this is the way to go natural of things.
