I have a Sony Ericsson K770i (think that's the right model).
Comes with Google maps. Yeah, I have to pay for data downloads. But I wouldn't use it much, just when uncertain of where I am. Takes maybe a minute to load and zoom in, I can see the satellite pictures or map view.
Dead useful if on a strange route and feeling a bit lost.