Intuitive navigation GPS app for a UK user
At the moment, there is no one single app that meets all of your needs, so I think you need to be looking at using a number of apps in combination.
I would suggest that you look at the following 3 apps:
Where To? - Discover your next destination
Each of these serves quite specific needs, but when used in conjunction provide a very comprehensive set of tools for exploring and navigating your immediate surroundings.
As for a full routing application, the only real option in the UK right now is Navigon. It is very accessible with VoiceOver, and quite intuitive to use. It has some resource issues on older devices, which make it sluggish and unresponsive, but on the more powerful 4S it is reported to work fine. Unfortunately you just missed a promotion, which saw the app reduced to £20, the cheapest that it has been for quite some time. Navigon tend to run promotions every couple of months, so you might want to wait for the next one.
I've tried the TomTom app in the past, and that was usable with VoiceOver, but there were still areas of the app that weren't accessible with VoiceOver. It also wasn't as intuitive as Navigon.
Avoid CoPilot, as that is totally inaccessible.
The maps are stored on your iPhone, so you shouldn't use any of your data allowance when routing. If you use the Google Local Search feature, that would use data, but only a nominal amount.
As for add-ons, I guess it depends upon how and when you will be using the app. If you only use it locally whilst walking, you probably wouldn't get much benefit from any of the available add-ons. The 7-digit postcode add-on can make entering locations easier, and the live traffic add-on could be useful if you travel longer distances by car.
As for other options, I'm not aware of anything new on the horizon.
If you fancy trying something else whilst waiting for the next Navigon promotion, you could take a look at VoxTrek Navigation GPS. There was quite a buzz about this app among blind users a couple of years ago, but now it never seems to get a mention. It's not been updated since July 2010, and it has quite poor reviews, so you should keep your expectations low. But, at £2, it's not exactly at the Navigon or TomTom level. Personally, I've not spent enough time with it to have an opinion.