It also depends on where you're starting from. As already suggested, you can mix a few things together and see if you find it inspires thoughts for a story; or, as happened to me in my current series, you start with a situation and have to look around for a setting. In my case it wasn't just a setting, but an explanation for the scene that I needed. Looking back on it, I can now see many different ways I could have explained that first scene. If I had sat down to write in a different frame of mind the whole story would have been different.
One of the constraining factors that writers of fiction face is the need to satisfy the reader. Very few writers are good enough to carry off something that isn't a traditional: "introduction, build tension, one or more climaxes, big finish and quick wrap-up" style tale. Looked at in this light, the vast majority of stories are the same. There are exceptions, but if you're hoping for success in fiction you have to pay serious attention to reader expectation.
One of the "tricks" is to obscure that standard layout so that it doesn't feel quite so standard:
- The tempting or mysterious prologue. (Though this is common enough to be almost standard now.)
- Interspersing your text with snippets of separate text relevant to the story. I've seen this done in various ways:
- definitions or reference texts (eg: Encyclopedia Galactica references in Foundation etc.)
- what the aliens/enemies/others are doing now
- what's happening now versus then
- narrator observations/interludes/interruptions
- Tell the story out of sequence
- Swapping character perspectives
- Have multiple threads going at once.
And these are all options that have little to do with what sort of story you're telling, they're just ways to give a tale subtly different feel.
Another way to make a difference is the style of language you choose to tell it. For example I love the way Neil Gaiman wrote "Stardust" - that almost childlike sense of a fairy tale about the story. Others have done it too. Or you can go the other way and take a fairy tale and tell it for adults.
There are so many choices it's a wonder a writer ever makes a start.