If you just DL the tiles for the areas of interest, I'm sure it could be done on a phone. DL'ing the whole US might cause a storage issue for phones though (though I hesitate to say this since many phones now have rather large storage capacity and SD cards, etc.)
EDIT: From the article:
Google Maps Navigation was built from the ground up to take advantage of your phone's Internet connection.
I don't think it's really reasonable, at this point, to expect a GPS device to work worldwide. Are they supposed to store the world's mapping data locally? Google is still licensing their maps from Tele Atlas (TomTom) outside the US so I don't think it's even possible for them to provide navigation in those parts.
The map downloading model you're describing already exists and there are already plenty of other companies providing in-car GPS devices for that. I don't think it's appropriate to implement that sort of thing in a smartphone since the entire point is that it should always be connected.