Pues... la verdad es que lo único que te puedo decir sobre Alcalá de Heneras es que lo que son gimnasios no te van a faltar. Pero de ahí a recomendarte uno... la verdad es que la mayoría de los que conozco de ahí son más orientados a artes marciales que otra cosa. Creo que hay uno cerca de la estación de tren. Y algún que otro he visto por ahí cuando he estado en Alcalá.
Hay muchos, pero no te sabría recomendar uno, puedes pillarte la guía que hay en esta página o directamente las páginas amarillas, miras lo que te queden más cerca y les echas un vistazo.