Por lo que dices, supongo que tienes una conexión de cable... en ese caso en España es bastante difícil encontrar un router+cable módem. Lo que si puedes encontrar es un router broadband o neutro al cual conectar tu actual cable-módem. El único inconveniente es que tienes que tener dos aparatos conectados, pero a cambio no tendrás problema ninguno con Linux (ni con ningún S.O. que soporte TCP/IP).
Personalmente te recomiendo el Linksys WRT54G, ya que además de ser muy estable, existen montones de firmwares no oficiales con los que podrás hacer auténticas virguerías a nivel de servidores... si algún día te diera la vena.
Saludos