Sin más datos... Es difícil decirte. Porque, nos da lo mismo Cádiz, que Vigo, que Gerona?
Yo tiraría una búsqueda en idealista, alquiler, toda España, ordenar por más baratos, e ir probando.
Pueblo donde veas un alquiler barato, búscalo a ver si tiene lo que tú necesitas.
Por ejemplo, en 5 minutos, he visto pisos en Baeza, provincia de Jaén, por 220€. 2 minutos más, y ya he visto que hay gimnasio y polideportivo allí.