I bought two last winter for my wife and I. We both love the S3, but as has been mentioned. There have been a few improvements in the S4, but not enough for me to consider breaking a contract or upgrading before my New Every Two time limit is up.
Basically it's personal preference. I would go to the Verizon Store and try them all out. I like the size, you can watch things like ESPN3 pretty well too. The S3's screen is virtually the size of the iPhone...the entire phone, and the S4's screen is 0.2 inches bigger than the S3's (on the diagonal). As I said not a big enough difference to upgrade. Another feature on the S4 is the resolution. It is 1080p as opposed to 720 for the S3. Again, not a big enough difference to change. Finally, The S3 makes a quality phone call. I know that smartphones do so much these days, but in the end the question is: Can you understand the person on the other end?
A cool feature that the Samsung has over the i-Phone other than size is the near device networking (though I think the iPhone is getting it at some point). You can beam apps, photos, games and contacts by simply touching the back of another S3. My wife and I use it all the time when we share pictures of our baby son.