I've got the Nokia E71 with Three for £20 a month including unlimited text and internet. The phone's metal-bodied, quick, reliable, good battery life, and the GPS is pretty quick at locking on.
It comes with Nokia Maps, which uses free maps that you can download onto the memory card - if you want voice navigation you have to pay a subscription, but it's not that good at that anyway and TomTom's a better bet.
However, and here's where the unlimited internet comes in - you can also install Google Maps for free - so you get stuff like satellite imagery. You need to be in 3G coverage but I've never found that a problem - and I've found Three OK. They used to not allow cancellation if you had signal problems, but that's changed recently.
I've also bookmarked the metoffice weather radar - so I can see whether there's any rain and where it's heading.
The phone's also a reasonable mp3 player.
It comes down to what you want from GPS. If it's voice navigation, TomTom's the leader - but if you just want to know where you are and/or look for pleasant routes while you're out and about (satellite imagery really helps here) I can recommend the E71.
http://threestore.three.co.uk/priceplans.aspx?id=1401&phonecode=NOE71G3DSL