[ainur]

I tend to think that the story would have turned out pretty much the same without Legolas or Gimli, but continuity of the story wasn't necessarily why they were there. Tolkien was trying to show his readers as much of Middle Earth as he could in the course of the story. Why else do we learn so much of the languages and history, even history that we don't really need to know, like the people of Rohan migrating from the north behind Eorl. Was it just so Tolkien could give them their own name for Hobbits? (Periannath--I think, I don't have my books handy.) Did Eorl know Smeagol's grandmother?
And how much would we learn of Dwarves if Gimli had not been there right along? They might still have found their way through Moria without him since both Gandalf and Aragorn had been there before, but would the tidings from the Book of Mazarbul have been as moving without him? I don't think so. Gimli's presence shows us a noble and gentle side to the dwarves that we could never get from the caperings in "The Hobbit." But the story would have proceeded just as well without him.
And Legolas gives us a different perspective of the Elves than we would ever get from Elrond or Galadriel. He is Moriquendi, a dark elf who never saw the light of the Two Trees of Valinor or ever travelled there. The "sea-longing" he speaks of in RoTK seems to me to recall the desire awakened in all the Elves to go the Valinor with the original summons of the Valar way back when they were still by the shores of Cuivienen. That may be a stretch, but his presence certainly instills a sense of history and age that transcends the 'timelessness' of Rivendell and Lothlorien. and so we see the elves from a new perspective. But still the story would have progressed without him, just not as richly textured or as moving. Tolkien wanted us to glimpse the bigger story that begins with the Ainulindale but never really ends, 'The Road Goes Ever On.' Tolkien wrote "Leaf by Niggle" to illustrate this point far better than I can express it.