I think Route66 is close, but I just wish they were there since they already have my money.
Wayfinder has North America maps, but I found that my street (that has been here for 7 years) is not on their map, YMMV. There is also the issue that you download the maps from them as you need them (thus perhaps large GPRS charges depending on your provider). I think you may also be able to cache them when you have a WiFi connection, but sounds like a pain to me.