Science fiction & fantasy stories, of course. What such stories best stand out in your mind?
ETA: Hit submit too soon.
I’m most specifically interested in stories that come down on the side of the future being ultimately unknowable, and destiny being crap; stories in which prophecies are of dubious reliability because there are so many possible futures, and all predictions are merely probability forecasts. But I’ll take tales in which the reverse is true as well.
It’s not science fiction or fantasy, but the first story I thought of is Oedipus.
“Singularities Make Me Nervous”, short story by Larry Niven.
There was an episode of either Twilight Zone or Outer Limits, in which a modern man suddenly finds himself in Washington on the day before Lincoln was shot. He tries to save Lincoln, with mixed results. It was based on a short story whose title and author I don’t remember. I haven’t seen the TV show, but the short story was good.
Well, it’s not your typical novel, but Kurt Vonnegut’s Breakfast of Champions definitely explores free will and determinism.
My novel, Staroamer’s Fate has that as a theme – the main character has only limited free will and has to do things that she doesn’t really want to do because they are her fate.
Of course, the movie Minority Report deals with exactly what you’re looking for.
It’s also an important point in Dead Again.
The oft-recommended The Time Traveler’s Wife.
I’ll add 12 Monkeys. A little based on the myth of Cassandra.
I also recomend Minorty Report but the written version. (Phillip K. Dick)
Slaughter House 5 deals with this a little.
Most of the books so far are the opposite of what the OP asked for, since they come down on the side of some brand of fatalism.
-FrL-
I’ll probably get laughed out of the thread for mentioning a manga, but I’ll do it anyway because it meshes with the OP:
RG Veda (why yes, the naming was on purpose). Basically, there’s this child and his destiny is to destroy the world. This was prophesied long before his conception, and his father is struggling with knowing his child will destroy the world, but he still wants his kid to be able to live. On a whim, he poses a question to another warrior in the kingdom: “Do you believe the stars can be changed?”. The warrior replies that for him, he’d move Heaven and Earth. But it’s spoiler territory as to whether or not he can. 
There’s the series The Belgariad, which features two conflicting prophecies, each mutually exclusive. Nobody knows which will win (spoiler: the good guys win). It’s not the deepest literature in the world and the sequel series, The Mallorean, feels like a retread.
I was just flipping channels on the TV, and I saw a scene from The Chronicles of Riddick. Judi Dench’s character is reputed to be prescient. The villain captures her and demands a reading.
“No one can really know the future.”
“Then tell me the odds.”
Technically, in Frank Herbert’s Dune novels, prescience was never infallible. The Guild Navigators and Bene Gesserit truthsayers saw possible futures and probable futures, but they believed that they could still make choices. At least until Paul and Leto II took power.
This far and no mention of The Terminator and all its related sequels and spinoffs?
That’s because from a dramatic or narrative point of view, it results in a tighter and more satisfying story arc. The alternative is too likely to develop a story line that ends by throwing it all away as an “alternate history that never really happened because someone from the alternate timeline acted to throw this reality’s timeline into a different course”. You know, the plot line for innumerable mediocre episodes of later Star Trek series.
It can be pulled off though. As noted, Terminator 2 basically follows the premise of the OP word for word, and the latter movies in the Back To The Future trilogy express the idea as well. And to some extent, Star Wars, as philosophized by Yoda. First he predicts that if Luke abandons his training on Dagobah to run to Cloud City, he would fall to the Dark Side: Only a fully trained Jedi Knight, with the Force as his ally, will conquer Vader and his Emperor. If you end your training now - if you choose the quick and easy path as Vader did - you will become an agent of evil.. Yet this does not come to pass, and later in the same scene he admits: Difficult to see… Always in motion, the future is.
One that may not quite fulfill the expectations of the OP, but might be worthwhile: Run Lola Run. No real spoilers below, but
Basic storyline: Lola’s boyfriend Manny is in debt to the tune of 10000 deutschmarks (or whatever currency), and has 20 minutes to get it, or he believes he will die. Lola decides that she will get the money, and takes off running…
The story happens three times over, and each ends up going off on a different path based on Lola’s choices, especially at the start when she chooses how to descend the stairs from her apartment. She interacts with the same characters in each telling, but based on the slight difference her timing makes, how she runs into them and affects them changes drastically. The film flashes forward on some of these characters each time-- in one telling, a given character may end up dying a pauper, the next telling, they may become a religious zealot, all based on how and when they run into Lola.
Now, the story goes off a bit from a pure idea of the future being unknowable, because Lola “learns” something in each telling that ends badly, and then starts over again, altering her choices to get closer to a future that works for her. But, it does play with the concept of free will vs. destiny, coming down firmly on the side of free will (at last Lola’s) and choice, and away from fatalism. Her choices, even those that seemingly are pointless, affect her future.
China Mieville’s UnLunDun fits your criteria pretty well. It’s supposedly a “young adult” book but I loved it (actually I love a number of YA books anyway…) - quite different from his normal style but very readable.
“Radiant Doors” by Michael Swanwick. It argues against predestination. Read it if you like, I was disturbed by it for days.