I run a rogers 3gs on bell, with 3g data.
I don't have any problems with speed. It's jailbroken and unlocked, it was a bit of a hassle so I say if you're gonna do it, make sure you do it right the first time, and you'll have a lot less trouble. Only issue is loss of GPS functionality. Even if you get the fix from redsn0w 0.9.9b6/7 for aGPS function, it might still clash with your service, and kick you off into "searching" or "no service" whenever you try to use the location services.
I just bring my iPad with me in my backpack or in the car if I intend to use GPS.
And I don't know much about the difference between iOS 4 and 5 for 3gs, I used iPad on 4, and got the 3gs on 5.0 when I bought it. But it is a HUGE difference on the iPad. I love iOS5.
I love jailbreak and will always jailbreak, but I mostly do it for iFile, and a the rest of the stuff is meh, kinda cool, but not important. For the most part, I run the phone the way it's meant to, with minimal modding. I do use speedIntensifier and SBSettings though. But to the point, I think iOS5 is worth it. I like it a lot. Notification centre is worth it all by itself, forget the rest of the updates!