The iPhone 3G is not meant to run 4.XX firmware. This is due to is almost "ancient" hardware (compared to whats out now). One thing you can do is turn of spotlight search. Go into Setting>General>Spotlight Search and un-check everything. Last piece of advice is, UPGRADE Hope this helps you.
if its jailbroken ,and you have multitasking now that may be a reason . You can try to a restore with a custom firmware without any extra options, or restore the withed00r custom firmware. This should make it work faster, let me know if you was able to do it, if not, I can do it for you online if you want, just send me a PM