En teoría deberías tener conexión en casi cualquier sitio. En pueblos grandes y ciudades irá mucho mas rápido, porque casi seguro que habrá cobertura 3g, pero en pueblos pequeños funcionará con GPRS (como un módem de 56kb más o menos).
Según la CMT, el "ranking" de cobertura es: 1-Movistar, 2-Orange, 3-Vodafone. Aunque hoy he escuchado en la radio que Movistar y Vodafone han llegado a un acuerdo para compartir las antenas.
En cualquier caso, si puedes probarlo primero, mejor.