>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.