Como dice Lukiluk, lo primero de todo, pero lo primero primero, antes de pensar en ejercicio e historias, es quitar la alimentacion negativa. Si quitas fritos, bolleria industrial, refrescos y alcohol de mas, cambiandolo por fruta y agua, bajas 5kg facilmente. Tambien ojo con la sal, que luego se retienen muchos liquidos.
Luego ya, si quieres perder lo que te sobra, pues a sudar. Yo pase de 89 a 75 en 6 meses, simplemente corrigiendo alimentacion, comiendo sin llenarme, solo hasta que ya me encontraba bien, y con bastante ejercicio variado (~6-10h entre semana, 5-10h los fines de semana). Bici, squash, natacion, windsurf... tu piensa que si no sufres, no sirve de nada. Al principio cuesta, pero una vez que coges el habito te quedas con ganas de hacer mas.
Lo que haces ahora es flojo... 20km no es nada, 25 largos (olimpica o 25m?) no son nada. Lo logico seria ver una evolucion... empezaste con 10km y ahora te haces 40km, o te hacias 20 largos y ahora 50, o hacias 3h de eliptica apurado y ahora haces 4 fuertes y te quedas con ganas de mas. Tienes que buscar ese punto mas alla, no hacer por hacer. Una vez que tu cuerpo se pone en modo energetico, los kilos empiezan a caer solos hasta que llegas a tu punto. Luego ojo no te pases... yo llegué a 73 y perdi masa muscular, ahora ando por 77-78.
Si no recuerdo mal, eras profesor o algo asociado a la universidad, asi q podrias aprovechar horarios e instalaciones, piensa en alternar gimnasio y piscina (las actividades que mas te gusten, al final es clave que tengas motivacion y te lo pases bien, pero cosas intensas), y los fines de semana alguna actividad fisica larga (senderismo, ciclismo...).
Respecto a alguien que opinaba que nadar y montar en bici no sirven para nada... yo "aplaudo" el consejo de recomendar a alguien, con 110kg y 42 años que no sabemos si ha corrido en su vida, que salga a correr "a buen trote". Quiere perder peso, no reventarse las rodillas.