Actually, you could fit the entirety of the state of Washington in <50% of my phone's storage.
I'm not seeing a problem.
Well, most people don't want to lose even 20% of their phone's storage in a single app, much less 50%.
And that's just for those satisfied to only have info for one state. What about people regularly travelling between 1-2 states?
That said, I question the OP storage math. At least with vector information, I know that something like Navigon's GPS/map app, can store the whole of US (including the smallest of towns and cities) in around 1GB.
If you're traveling regularly between two states, you'd want your origin city, destination city, and your route with maybe a couple miles on either side. Say a 250-mile route, and 200 square miles at either end. I bet it fits in <2GB.
Here's a great tool for getting a feel:
http://tools.geofabrik.de/calc/#type=geofabrik_standard&bbox...
Z=18 is rarely used, so for Z<=17 you're looking at roughly 300MB for raster tiles a city the size of Calgary. You also don't get routing information with purely raster data.
You could try vector data which would be smaller, but then you have to display it, which can be computationally expensive if you want it to look pretty, and you'd lose the snappiness you're seeking.