I'm on AT&T and for the most part I agree that simultaneous talk/surf is not a huge deal, except if you tether. I tether my iPad and laptop through my phone frequently, and it's nice to be able to take a call without that dropping out.
Plus as you mention the AT&T speeds are "potentially" a lot better, but actually only about 2X faster than Verizon where I live.
Since I have good AT&T coverage around here that is the best choice, but if I didn't and had to use Verizon, for the most part it wouldn't bother me (just the potential for data interruption while tethering if a call comes in, that's somewhat picayune).