I would go with Evo. If Sprint and Verizon both have coverage where you need it, then there is no thinking about it, in my opinion. Sprint is the way to go.
I have tested Verizon's speeds in web browsing vs. Sprint's 3G using dslreports.com and Sprint ALWAYS 100% of the time came out faster. In several cities.
Also, you will be paying $79 for Evo per month for features that will cost you about $140 on Verizon. (GPS, TV, MusicPremier, etc... Plus text, minutes, web)
the Incredible is a great phone, but the Evo has everything the incredible has and more..... For less money per month. It's a better deal.
I say get Evo with Sprint. No question about it.