Determinism vs. randomness.
If my choices are not deterministic, they must be random. I would rather be deterministic than random. In any case, if they are random, it means that I don't have free will either.
I like to think that all my choices are a result of the past; my genetics, my childhood upbringing (that I don't even remember, but which formed the neural pathways in my brain), my early memories, my environment, education, experiences, friends, knowledge that I have absorbed from the world... In each and every moment, I make a choice, which is the best choice I can make given my brain power/structure, my motivations and the external constraints given (is it raining? can I fly? when do I need to pay the rent). Even my motivations are largely determined by my genetics - avoid pain, strive for pleasure. I definitely hope that my choices are not random.
How does morality come into play, if our choices are deterministic? It doesn't - my morality is my internal concept that I use to make choices more quickly/easily. I don't impose my morality on other people and I don't really care how they make their choices, but I support different forms of punishment that modify the incentives of other people so that the society can function.
Finally, I don't think that the future is predictable, even though it is deterministic. Like you don't know what 1048936701349 * 13046871435 is before you calculate it, like even the computer cannot predict the result before calculating it (i.e. the fastest calculation algorithm is also the fastest prediction algorithm), the same way we cannot predict the future before it happens, i.e. before the universe "calculates" it.
But this is not what is classically understood by free-will, and I suggest that it is your dilemma which is false. Quoting Aquinas, "Free-will is the cause of its own movement, because by his free-will man moves himself to act."
I anticipate that free-will thus understood is likely ruled out a priori by your philosophical disposition. Nonetheless, I think you can perhaps come around to see that is logically opposed neither to determinism nor randomness in the human brain as observed from an objective standpoint.
I'm happy to be challenged on my philosophical disposition though, because I'm aware that there are whole schools of thought that seem like vague informal nonsense to me, and I'm not so arrogant as to assume I'm simply smarter than them.
 I don't understand relativity well enough to adapt my argument to it, so I'm happy to accept a counterargument there.
Note that from the outside, free-will is by definition apparently "random". It is a black box not determined by any variables in the greater world.
What matters is that the free-will is mine or yours-- that the entity known as to me as myself or to you as yourself should also possess this power of determination which to the outside world appears random.
To witness to the lack of a logical incompatibility with determinism, you can posit a model wherein the will does something like project itself in both time directions in such a way as to keep up the "illusion of determinism". Not that I think such a mechanism is actually in place; this model is just to show there is no logical contradiction, and there could be other models that do the same.
I am entirely happy to accept that free will is compatible with determinism, and it sounds like we have similar views on this issue. Personally I consider ownership of "will" to be a far more important notion than that of some abstract metaphysical "freedom".
Free-will is a third possibility opposed to determinism of choice and pure randomness of choice.
But it is compatible with a either a deterministic or a probabilistic universe.
My choice of the feminine above was a choice, but not one everyone would make. So how could it be anything but determined by who I am?
The other major interpretation would be that out of the possible futures one is randomly selected based on its probability. Determinism without branching doesn't seem like an option given the laws of physics, correct me if I'm wrong anyone?
This comment goes into more detail about what we do know: https://news.ycombinator.com/item?id=7069261
Also, if we were being obtuse, we can describe any (finite) probabilistic universe as a deterministic one with enough rules.
We're pretty close actually. Look up Bell's Theorem (http://en.wikipedia.org/wiki/Bell's_theorem). It has been experimentally verified countless times and necessitates that "one is forced to reject locality, realism, or freedom". "Freedom" meaning something specific in a scientific sense. Rejecting the last one implies something called superdeterminism, which is basically just determinism (the "super" implies that everything that exists is deterministic; there are no random components). Gerard t'Hooft is one of the only legit physicists left who supports a superdeterministic theory. Almost all other physicists believe that a measurement of a quantum state collapses it into a random eigenstate.
For me personally, were superdeterminism found to be true (although it's looking more likely that's not going to be the case) it wouldn't bother me in the slightest, and I don't see a conflict between determinism and free will. Imagine someone creates a movie. They decide the plot -- what happens and when. They decide the setting, the number of characters, and everything else about the movie. Then when you play the movie, everything that occurs is predetermined -- deterministic in a sense -- yet it was freely chosen outside the realm of the movie. I kind of view reality that way.
Along the same lines, how is determinism vs. randomness any less of a false dilemma? You say "if my choices are not deterministic, they must be random." But the concept of free-will is another (well established) alternative to determinism.
We have already entered into an old metaphysical forest here, so why not go ahead and think about what exactly randomness is? From the way you describe the "more important" dilemma, randomness is a sort of determinism - when viewed at a systemic level. That is, we often speak of randomness in the terms of probability, as though the mathematical probabilities of a phenomenon are the a priori governing laws that determine that phenomenon's taking place.
An alternative way of seeing random probability is that the laws governing a system are simply unknown to us - though they are determined. We can calculate a-posteriori probabilities of a phenomenon, but it is not the probability itself that governs the system. This is the crucial point.
For example, assume that humans have free will. My favorite sandwich shop serves Reubens on average once every 18 days. But let's further say that the shop owner has some idea to sell Reubens 20 times a year.
Whether the universe is truly governed by random probabilities, or whether the real will (shop owner's) governing the system is just a black box to me, the calculated probabilities look the same.
So I suggest perhaps that yours is also a false dilemma. There seems to me no necessary implication of non-determinism and randomness, because I view randomness from an epistemologically humble position, i.e., that it is an a posteriori description of our lack of understanding.
Maybe in so much as randomness solves the false dilemma of free-will vs. determinism, free-will solves the false dilemma of randomness vs. determinism. A trilemma, perhaps?
You can, if you are stubborn, create a theory of QM with non-local hidden variables, but it turns out to be just as weird as orthodox QM; but instead of accepting objective randomness, you have to accept faster-than-light interactions. One example is David Bohm's "pilot wave" theory. 
I can live with that :)
In what way will an entity that has free will behave differently than both a fully deterministic entity and an entity that is deterministic excepting occasional random events?
I have yet to see either an answer to that question, or a definition of free will that leads to one. Until then, I consider all speculation and meditation on the "revelation" that we have none to be a tale full of sound and fury, signifying nothing.
I'm more curious about what you guys think. I've long thought the arguments against free will are much stronger than those for it, but it's an unsettling idea to live with.
Regardless, if anyone finds the thought that an FMRI can detect you making a decision a significant amount of time before you're aware of making that decision particularly interesting, this book dives into that research and much more about the nature of consciousness from a neuroscience and information theory POV:
Also, lately I've been hearing a lot about http://en.wikipedia.org/wiki/The_Happiness_Hypothesis
in which the brain is likened to a person riding and elephant. We can train the elephant, but mostly the elephant repeats its program.
It's billed as about "happiness," but imo that's only one slice of it. It applies to all habits, including eating, exercise, improving sw development skills...
Some of the stuff is a but uneven but he's written some of the most thought-provoking sci-fi I've read in some time.
I later tried to recommend it to my mother, but found myself incapable of doing so.
So if this "predictor" is nothing more than a circuit that sends information to itself in the past, there must be a "me" that pressed the button without seeing the light, before the data is transmitted to the past to the "me" that then sees the light but at that exact point splits off into a separate timeline. And then I would have free will again.
Of course I am assuming time travel where travelling forward in your own timeline is impossible, something the article seem to not really go into.
Imagine the predictor works, what does that mean? One second prior to the action, the course you would take is set. This is actually probably a point in favor of the possibility of freewill; humans are course-taking machines, we have a whole life (and our evolution before that) to acquire dispositions that will one day help us survive. What kind of freewill do we want? Do we want to be "free to dodge a brick when thrown at us" or "free, one second before the brick arrives, to duck or not duck". Which of these is the important one? The kind of freewill we really want isn't the kind where we are free floating actors, it is the kind where our history, personal and evolutionary, dictates our present. The point is, real freedom is not about being without limits, it is about having sensible responses to ones environment; creatures evolve the freedom to avoid being eaten, the freedom to anticipate others' actions, the freedom to manipulate other agents with our clever words. Dan Dennett makes a better case for this than I, please look into his wonderful books on the topic.
When you think about it, it is what I would expect. Your awareness is the product of nerves firing, so they have to fire before it can be reflected in your consciousness. If you decide to recall some information, the neurons storing that information have to be activated (they have to fire). If you can create a device (and we have) to detect those nerves as they are firing you will know what person is trying to recall before (by some miniscule lead time) they are aware of it.
These may seem like contrived examples, but when you eliminate all outcomes that aren't self-consistent, it may be that _all_ the remaining possibilities are contrived. Probability gets weird when time travel is involved.
Determinism isn't something I've explored quite satisfactorily enough just yet, and reading articles such as this one sends me straight back into the depths of the literature.
So by inventing your mechanical device you haven't added any information to the puzzle, only confusion.
I think Searle's Chinese Rooms employs the same fallacious way of thinking to refute strong AI.
"If you drink it, something surprising is bound to happen which makes you spill it on yourself or someone else. But it's charmed to vanish just a few seconds later"
Still, I don't see why the Predictor couldn't work in the same way - how would you determine that it doesn't?
This would be true one second ago, and a second ago this would be true about the second before that.