while I wouldn't recommend Verizon, I will tell you my experience

I have an E815 that I've enabled dialup networking on (http://www.zdziarski.com/papers/v710info.html). I can connect using EVDO (or their slower data network if EVDO isn't available) for the cost of minutes - nights and weekends means free internet access when free wifi isn't available. In a jam, this works well for getting a connection.

That being said, I don't know if you can reliably get an E815 anymore, and most of Verizon's phones are crippled beyond belief. I haven't been able to find a data plan which allows tethering and which isn't stupidly expensive.

i'm really looking for a data plan that's <$20 a month for unlimited (or nearly unlimited) data, but I doubt that's going to happen any time soon.