Sprint also has agreements with MetroPCS and Cricket if you are in one of their markets, although chances are if you can't get a Sprint signal, you can't get those carriers either--so you're on Verizon.
Sprint's data did go through a really bad phase for a little more than a year after having some of the fastest 3G data available, regularly beating Verizon (I've had Sprint since 2002)--they are working on it, and it's getting better and better. I'm back up over 1mb. regularly on 3G so they've done a lot of the upgrades they said they have been doing and I am happy. It's not quite to where it was before they had the big crush of smartphones--but then again, a reasonable 1 meg connection is acceptable on 3G since I'd rather see them invest that money into launching LTE vs. getting EV-DO back to 1.5-2 meg for everyone.
I think you'll be happy... you might have some slowness initially, but I think they are making progress--and if you get an LTE phone (out in early May), you'll be ready as soon as it launches in your market. Unlike WiMax, LTE will be launched on all existing towers so the 4G coverage should match the 3G nearly exact.