iOS4 was horribly slow for me, until I jailbroke and enabled multitasking (NOT the background - this slows things down a lot)... Multitasking made stuff a bit snappier again, until you have too many apps open, then you have to manually kill them for some reason. This is weird, since normally these apps should have been suspended to disk? Maybe it has to do with the cache-size of apps that stay in memory, which is a bit too big to fit in the 3G's 128mb RAM?
This could also improve things: doing a hard reboot (holding home + lock until it reboots - don't slide to power off) and when +- 15 seconds in the reboot process (with the apple on the screen), hard reboot again. I saw someone suggest that this would clear all saved app states and speed up things too. Not sure if this is true, I jailbroke my phone too quickly after that to be sure this would have helped somethings.
I do know that multitasking clearly enables you to access applications that you use a lot a lot quicker. I usually keep my phone & messages apps open at all time, and kill the rest.