An iPod Touch isn't going to replace a mobile unless you don't make calls on it.
I think you'd be pretty happy with a 5800, it's a good music phone and since it runs Symbian (like E and N series Nokias), there's loads of apps - including games - for it. Check either O2's own website, or a third party one like Gameloft. There's also a bunch on Ovi, Nokia's app store.
The web browser is based on the same core as the iPhone's browser, so it'll render pretty much the same. Symbian phones also support Flash, whereas the iPhones don't, so I personally find it a better browsing experience. The 5800 also has a higher resolution screen than the iPhones and iPod Touches have, albeit with a resistive rather than capacitive touchscreen.
Throw in a superior camera to that of the iPhones, cheaper tariffs and fewer platform restrictions (yay for Flash and Java!) and you'll find that a mid-market phone matches and in some ways outperforms an expensive high-end phone. But the real clincher for me would be the unlimited music downloads from the Nokia Comes With Music package. If you're going to be legit and pay for your music downloads, then Comes With Music is way way better value than iTunes.
The choice is yours. So how much do you value the cool factor of the Apple logo?