For 3g iphones, IOS 4.x is not suitable for 3g, it will still be lag and slow and unreponsive when RAM resources is almost fully used.
You can try to restore to custom firmware of 4.2.1 to see for yourself. The reason why i say custom firmwware is because you have the ipad bb update and you cannot restore to stock 4.2.1 firmware.
If do not wish to go for IOS 4.2.1, then you can always restore back to stock 3.1.3, and do the jailbreak with redsn0w 0.9.4 but browse to 3.1.2 ipsw. Make sure you setup as a new iphone.
Thanks a lot for your suggestion. I think i should restore to 3.1.3. I would like to know if i need a custom IPSW or a stock one. Could you please post the guide/download links please.
You can restore to stock 3.1.3, error 1015 will pop up, use Exit recovery from the feature of tiny umbrella to kick it out. Now you can jailbreak it with redsn0w or jailbreakme 2.0 from safari on your iphone.
If you want to jailbreak it with redsn0w 0.9.4, when you are asked by redsn0w to look for firmware, browse to stock 3.1.2 and then rest is very easy from the instruction.
Do your unlock again from cydia by installing Ultrasn0w.