I'm also in favor of a phone with GPS.
Here in Finland we have Nokia's 5230 with free navigation (3.2" touchscreen). The phone without a contract is 130€. Don't know how much it is if it's subsidized. Well, I think nowadays every new Nokia phone comes with free navigation (assuming it has GPS-chip).
Don't know about accuracy. I have a 6220 Classic, never had any problems with that, at least. Though there aren't that many tall buildings around here (or at least not that close to each other that it would matter...).