Please identify the first Sci Fi book or movie that mentions or utilizes Lego in its story line in a distant futuristic setting.
A candidate for one of the first depiction of legos showing up in a far-future setting (unlike Time Bandits, where the lego-like blocks appear in a Fortress of Ultimate Darkness from the "Time of Legends" which seems to be outside of normal history, though the main characters have access to time portals so they bring some weapons from future ages for a battle there) might be the story Dramocles by Robert Sheckley, published in the March 1983 issue of Isaac Asimov's Science Fiction Magazine. I found this excerpt which reads:
"What other signs of his love does Prince Chuch send me?"
"My spaceship is loaded with gifts for you and your nobles," Vitello said. "There are Erector and Lego sets, puzzles and riddles, comic books, a selection of the latest rock recordings, Avon cosmetics for the ladies, and much else besides."
The excerpt itself doesn't show what story it's from, just that it's from a volume collecting the 1983 issues of Isaac Asimov's Science Fiction Magazine, but looking for references to the character of "Prince Chuch" mentioned above, I found this excerpt from the same volume which refers to "Prince Chuch, eldest son of King Dramocles", so it must be from the story "Dramocles". This story was published (or expanded) as its own book later in 1983, titled Dramocles: An Intergalactic Soap Opera. Out of curiosity I picked up the kindle version on Amazon, it seems in this version the reference was changed to "Leggo sets", whether a typo or out of wish to avoid copyright problems. But skimming around it's clear it does take place in some distant future, for example here's an excerpt that refers to civilizations on multiple planets and the "ruins of Earth":
The call never came, and Haldemar grew to despise the fickle superficiality of the warm-planet peoples. His deepest desire was to let loose his lapstraked spaceships upon the effete civilizations of the inner worlds. But the inner-planet peoples had too much going for them. They had deadly weapons and fast ships scavenged from the ruins of Earth, and they banded together whenever the Vanir attacked any one of them.