Downgrading iPhone 3G 4.1 to 3.X or 2.X
Firstly, if you don't use spotlight (the search screen when you swipe right from Home) you can turn that off which should increase the performance of the iPhone.
Settings>General>Spotlight Search and then deselect all of the options.

If you still want to downgrade....

The iPhone isn't really designed to downgrade but there are ways to do it. 

I had to down grade from the 4.0beta to 3.1.3 and followed this guide on The Unofficial Apple Weblog.