C.S. Lewis discusses this (in "Mere Christianity" I think).
Basically he says that Jesus (and God) can see into the future, since they are "outside of time."
If that's true, then no paradox - as you said, you have free will AND Jesus/God know how you are going to choose.
But He did create the Universe and so He had something to do with how we ended up. If the Calvinists are right, then He decided ahead of time who would end up in Heaven regardless of their free will. But I've noticed that people tend to be in one of two camps: they have more universalist beliefs and think that most people are going to eventually end up in Heaven which seems too merciful, or people tend to believe that their particular set of beliefs is imperative for salvation and so very few end up in Heaven which seems too unjust.
The general response is to state that God's knowledge/mercy/justice is so far above our understanding that we shouldn't try to explain it. We should just hope and pray that God will give us the grace to be saved. That seems a bit too antinomian to me.
This is one of the answers to the Problem of Evil, i.e. that no matter what horrendous and seemingly unmerciful and unjust atrocity is visited upon a person there is a good reason that God allowed that to happen.