Nokia does not support Google maps. It has its own version called Ovi Maps.
What you should be aware is that Nokia Navigation is free after you have downloaded the maps. Also you can download all of the maps available (about 180 countries) for free. Ovi Maps is an excellent phone app.
Now you should go for the iPhone 4S. Much easier to use than any of the Nokia's on the market. It also has good battery life and Google Maps come as standard.
You can also get apps for the iPhone if you want turn by turn navigation rather than just a map app.
As google maps is native to the iPhone you will also find that a lot of storefinder apps have Google maps included that can then help you find a specific store.