Yo creo...

... que el cambio (si es que se puede hablar de cambio) se produce en Lothlorien. Hasta entonces permanece entre ellos un cierto rencor ancestral, que en el trato del viaje se va limando, y que es el trato especial y comprensivo de Galadriel hacia Gimli lo que conmueve a Legolas. Ya tras dejar el bosque van juntos en el bote, hay gestos claros de complicidad entre ellos, al encontrarse con los jinetes de Rohan es cuando Legolas pone su vida en peligro por defender precisamente a Gimli, y aunque persistan las bromas y "piques", su amistad permanece ya por encima de cualquier tipo de rivalidad.