There's one oddity that's worth noting before I get started. The 1994 Nebulas were the last time that the Hugos and Nebulas for short fiction shared two or more awards. In addition it would take until the 2001 Nebulas for the two awards to agree on any story. At the same time in the novel category there was a ten year long disagreement. So after here it is territory where the SFWA and SF fandom didn't agree.
1993 was a year for light fantasy; both of the unique winners that year could have easily dropped the fantastic element in the tale and still had most of the same concepts...
"The Night We Buried Road Dog"
by Jack Cady
1993 Nebula Award for Best Novella
On the lonesome Montana plains during the early 1960's lived eccentric men who swear by their automobiles and pass rumors between them about a legendary wanderer who is only known by the name "Road Dog". One of these men starts an auto graveyard for burying beloved cars. When another has a strange face to face encounter with the Road Dog he flees the region but finds himself being drawn back for a confrontantion.
The plot itself in this story isn't much but Cady does a great job with character and mood. Instead of just being a collection of quirks Cady doesn't forget that they need to be interesting characters first. So while one of them may love cars so much he sets up memorials to them that isn't the only thing there is to him.
As for mood a big part of that is how well Cady establishes his own kind of Americana folklore. The souls of those who died at the roadside appear just off the headlights to distract weary drivers. Ghost cars roam the lonely highways late at night appearing from nowhere and vanishing in the distance. The mysterious Road Dog communicates through obscure messages left on rest stop toilet stall walls. The story borrows liberally from urban legends and uses them to good effect.
For a story about fast cars this is a very leasurely story. I think that works for its purpose, though. It's about men leading a lonely existance in the wilds of Montana where time passes slowly. Cady was so evocative in "The Night We Buried Road Dog" that I think it easily overcomes the less interesting plot. I enjoyed it quite a bit.
by Joe Haldeman
1993 Nebula Award for Best Short Story
Tied for 1993 World Fantasy Award Winner for Best Short Fiction
During the Viet Nam was there was a soldier assigned to body recovery and identification. An officer too flush with his own power demands that he go into the field to a firebase for immediate removal of corpse. Once there the soldier finds two bodies, an American and a strange looking tribesman and before he can investigate further he becomes caught in a firefight.
I know that he's just drawing on his experiences but Joe Haldeman captures the feeling of the military better than any SF writer out there. "Graves" puts that on full display and though it uses a lot of familiar cliches Haldeman can tell those and make them interesting.
This is a very short story and in this case it barely qualifies as fantasy. In fact the fantasy element is so light that I suspect it was applied just to sell the story to a magazine. Still it is well integrated; it doesn't feel like a bolted on monster thanks to the resolution in the last few paragraphs. I have my own theory about the nature of the story and since it would spoil things I won't go into it; I will, however encourage you to read "Graves".
"A Defense of the Social Contracts"
by Martha Soukup
1994 Nebula Award for Best Short Story
In the future civilization has changed so that everyone registers their preferred sexual habits. The idea is so that there could be no deception when, for example, a polyamourous person meets someone looking for a committed relationship. When one woman falls in love with a man registered for in discriminant sex she schemes to force him to be monogamous.
This is classic SF in the "posit a strange thing about a society and explore the consequence" mold. I've got to say a society where sexual behavior is both incredibly open and enforced is an interesting one. The concept includes how the story is told; it is done as a cautionary tale that is remote and passionless. It results in one of those interesting situations where things the problems of our world are replaced with a new set of complications.
I understand what Soukup was doing with the style she chose for this story, I just found that it made it hard to be interested in the characters. I suspect that she wound up doing this because that main character is fairly unpleasant and disconnecting the reader from them would avoid "taking sides" in her argument. Either way the prose wound up being technically interesting but dull to read.
For that reason I cannot just recommend "A Defense of Social Contract". If you're like narratives with unique styles then you may enjoy the story but I think that it will fall flat for most readers.