I don't discount the value of GPS when travelling. That's the 1% of your life where you are "lost" compared to the 99% part where you are not. However, your example doesn't really work because the iPhone's EDGE data won't really work in Europe (I believe that's correct: the phone will work fine, but not the data). I'm not really a homebody, but I don't know what crazy awesome job you have that lets you travel to Europe for more than 2 weeks out of the year.
I live in Los Angeles. It's a big city, but it would be pretty hard for me to be completely and utterly lost in it. I could map any location relative to some LA landmark by default (LAX, UCLA, etc.) and be able to get there just fine. Or I could take the two seconds to input my exact cross streets and get perfectly accurate directions. I see the convenience in avoiding that last step, but my point is that if you're near where you live or work (which is 99% of the time) you don't really need that level of precision. It's hardly a deal breaker. Without GPS, perhaps once a month when I'm venturing somewhere I need to type a new location. With GPS, I can avoid that step. Cool, but not nearly enough to matter all that much.
I guess we differ there, since I spend at least 2 months per year in places I never or very seldom have visited. I am always short of time and I can afford the luxury to get lost. I have no ideas where to eat and what is available. I am often ignorant what could be interesting for me to see/experience in the city I am in.
Same thing when I am on vacation. Little time and I want to be able to see as much as I can the short time I am there. Finding good places to eat can be a b***h. If you happen to stumble on a nice place you might want to go there again. Try to do find that small restaurant with the strange name in e.g. Cairo.