Rob - if you'll never put movies on and don't have a large music collection you can probably get by with 16GB. Some games and GPS apps can also take up a good amount of space, otherwise most apps are pretty small. 32GB was worth it for me to have more music.
I'm pretty excited to have Verizon as an option when my 3GS AT&T contract runs out this summer. It's exactly why I was reluctant to sell my iPhone to upgrade to the iPhone4 - the new features weren't worth being stuck for 2 more years. No LTE in the near future is a bummer though, I doubt the iPhone will get it till 2012 so I may want to try out the new Droids first and see how good the speed increase is.