I recently read a short story that was one long letter from one character to another. The structure inspired me. Are there other interesting story structures like this that I just haven't come across?

Welcome to the joys of the epistle! An epistle is a letter, usually a more formal work that is shaped, as opposed to a chatty, private exchange. An epistolary story (or novel) might unfold as one long letter or a series of letters from one or more characters.

Plenty of writers have experimented with structure with much success. Daniel Orozco's "Orientation" is told as a first-day tour of the workplace for a new employee. Here’s how it starts:

Those are the offices and these are the cubicles. That's my cubicle there, and this is your cubicle. This is your phone. Never answer your phone. Let the Voicemail System answer it. This is your Voicemail System Manual. There are no personal calls allowed.
The tour quickly veers into the more personal territory:
Russell Nash, who sits in the cubicle to your left, is in love with Amanda Pierce, who sits in the cubicle to your right. They ride the same bus together after work. For Amanda Pierce, it is just a tedious bus ride made less tedious by the idle nattering of Russell Nash. But for Russell Nash, it is the high-light of his day.
Lorrie Moore's "Amahl and the Night Visitors" is organized as diary entries:
11/30. Understand that your cat is a whore and can't help you. She takes on love with the whiskery adjustments of a golddigger. She is a gorgeous nomad, an un-friend. Recall how just last month when you got her from Bob downstairs, after Bob had become suddenly allergic, she leaped into your lap and purred, guttural as a German chanteuse, familiar and furry as a mold. And Bob, visibly heartbroken, still in the room, sneezing and giving instructions, hoping for one last cat nuzzle, descended to his hands and knees and jiggled his fingers in the shag. The cat only blinked. For you, however, she smiled, gave a fish-breath peep, and settled.
And later:
12/4. Sometimes the phone rings, but then the caller hangs up.
In "Facts Toward Understanding the Spontaneous Human Combustion of Errol McGee," David Means focuses on the evidence of what was left behind to reveal something about McGee’s life. The story is broken up by subheads, including “The Fire,” “The Skull,” and “General Conditions.” One section, “Additional Theories: The Spiral Notebook Theory,” reads like this:
Word was McGee had a fascination with the idea of the spiral notebook, and even claimed that he had invented the product himself . . . One old timer remembers seeing him in the break room during his electrician days, fiddling with wire, twisting it around a dowel. Only through stubborn will is it possible to fit McGee’s obsession with the spiral notebook with the manner in which he died that evening at the lake, and in doing so one must turn to the grand theory that includes the idea of symmetry and of the spiral in relation to the stress—and heat and friction—produced by certain bond papers when a sheet is torn away. But that’s a stretch.
David Foster Wallace's "Brief Interviews with Hideous Men" reads as a transcript of the very title. Each interviewee elaborates on a "hideous" characteristic. Wallace includes only the answers, not the questions that prompted them. Tim O'Brien's "The Things They Carried" tells the story of a platoon in Vietnam by relying on lists that document necessities, both physical and emotional. Junot Diaz's novel The Brief Wondrous Life of Oscar Wao uses footnotes to elaborate on moments in the narrative. And there's the graphic novel, which combines written and visual storytelling elements.

In terms of structure, you're limited only by your imagination.