Android FTW!
You'll be MUCH better off in the long run with any number of the android based phones available. the iPhone 4 is already outdated and slow, and the 4s is just a stopgap until they get the 5 together. Verizon offers multiple android phones (with 4G LTE speed that iphones don't have) with larger screens, more memory, and better performance.
- Justin