Artificial square ices are structures composed of magnetic nanoelements arranged on the sites of a two-dimensional square lattice, such that there are four interacting magnetic elements at each vertex, leading to geometrical frustration. Using a semianalytical approach, we show that square ices exhibit a rich spin-wave band structure that is tunable both by external magnetic fields and the magnetization configuration of individual elements. Internal degrees of freedom can give rise to equilibrium states with bent magnetization at the element edges leading to characteristic excitations; in the presence of magnetostatic interactions these form separate bands analogous to impurity bands in semiconductors. Full-scale micromagnetic simulations corroborate our semianalytical approach. Our results show that artificial square ices can be viewed as reconfigurable and tunable magnonic crystals that can be used as metamaterials for spin-wave-based applications at the nanoscale.