Well I used to have an iPhone 3G and when I upgraded it to iOS 3 it was painfully slow. So what I did was this:
1) Switch off spotlight search (Or some elements of it) - Settings -> General -> Spotlight Search.
2) Reduce the amount of mail accounts being fetched to only the ones I needed to be fetched.
3) Try and keep minimal tabs open in Safari i.e. Don't leave all 8 open, keep closing them once you're finished.
4) Reset network settings at least once a month - i've found this also helps when you have no service, it just comes back instantly for me sometimes.
5) Try to use applications that are less resource intensive. This means stay clear of things like Infinity Blade.
6) Try to minimize how many calendars, contacts etc you have syncing.
7) Upgrade to iPhone 3GS/4/4S - they are all faster, the iPhone 3G has a slow processor.
I hope this helps. This really helped me speed my iPhone 3G and make certain applications usable a few years ago.