The cost of the extra memory is a fraction of the cost of your monthly phone+data bill. $200 difference between the 16 and 64, right? Amortize that over 24 months, that's $8.33 / month. Now consider the voice and data and tax costs per month. I'll guess $83.30 / month, so 10%.
If you get a GPS app with standalone maps (Navigon is one) you'll need about 1GB for that, as I recall. I think the consensus of this tread is: at least get 32GB. And if you're thinking of watching stored movies on it, want thousands of tunes, photos, apps, etc. move up the 64GB.