What's surprising is that it's gotten so much slower without any new functionality! I'm convinced that Apple has added some code to slow it down just to get me to buy a new one tinfoil hat.
iOS 4 on the 3G seems almost unusable and with little additional features I wonder why Apple bothered with it. There are downgrade tutorials around I'd suggest looking at them.