I've just got myself an HTC Wildfire and am really happy with it- ~£150 or so and I prefer it to my GF's £320 Nokia N8. Easier to use, more tactile, more apps, less glitchy and just overall nicer!
I've gone with Giffgaff as a service provider which I'm also really happy with so far- kind of pay as you go but you also buy 'goodybags' which can be added to give extras. I've stuck £5 credit on and bought a £10 goodybag which gives me 250 free minutes and (truly) unlimited data and text messages so in theory I'm kind of on a £10 per month rolling contract with full on unlimited web and texts which is spot on for me.