Realmente lo que pides es lo normal. La mayoría de omv y segundas marcas dan 20-25gb e ilimitadas por 20€.
La Inimitable de Pepephone (25gb), Lowi (23Gb), O2 (20Gb)... Puedes probar, además, porque no suelen tener permanencia, así que si ves que por cobertura o lo que sea no satisface, pasas a otra.
Yo a nivel personal estuve 8 años en Pepephone y me caían bien... Cambié por meterme en un pack con fibra+tv, pero si no seguiría con ellos porque realmente nunca tuve problemas. Lowi y O2 pueden dar confianza por el hecho de ser segundas marcas de las grandes (Vodafone y Movistar respectivamente), pero vamos, que...
Problemas puedes tener con todas o con ninguna, no existen garantías, solo suerte. Y viviendo en A Coruña dudo que haya problemas de cobertura de ninguna, al ser ciudad grande. Así que la que más rabia te de...