In the Halls of the Martian Kings, by John Varley
John Varley was the Ted Chiang of his generation. I've been meaning to read this story for a very long time now, and now that I finished it, I can say that it hit all the boxes. What was really strange about it was its atmosphere of optimism - it was almost Clarke like in its mixture of cosmic indifference meets human awe.