I too am having these issues. I had one 3gs with insurance at the end of my 2 yr contract I had it replaced for a new one and both of them had this sluggish behaviour with IOS 5.
My main issue with this, other than its a bind waiting for something to happen after pressing an icon or a letter on the keyboard etc, I've recently started playing facebook/zynga poker a lot lot more than I used to cos its very convenient on my phone through my wifi connection, but, I've lost loads of chips because the game play becomes unresponsive and eventually crashes. I play in sit n go tournaments where top 3 finish gives decent payback but my iphone starts freezing and then it crashes and I loos my seat at the table and all my chips, my stake and any prize money I would have won.
Also, other players at the table get annoyed with me because I cant do anything and the timer goes down all the way before it folds on my behalf and the next player at the table gets his chance to play.
I turned iCloud off straight away after update and not for handset speed issues but because I dont have any other device that would benefit from using iCloud and just like bluetooth, if you dont use it, dont activate it.
After reading through this thread, I've turned off every notification for apps that I dont use or need notifactions for so I'll see if that changes anything.
I do like the response I read earlier although I cant temember who posted it, about the 4S having a superior processor and memory and it does make a lot of sense, but what would also have made a lot of sense would have been to have a warning when upgrading to IOS5 on a 3GS explaining the potential problems.