How do Christians reconcile God's omnipotence with his omniscience? If God is truly omniscient as in "all knowing", then God knows everything including the future.  But doesn't this then remove his choice to do something other than the choices he takes in the future he knows of?  In which case he is not omnipotent?  Or conversely, if he can truly do anything because he is "all powerful", this has to make the future uncertain even to himself.

How can these two common claims about God be reconciled?

(There are definitely different ways to interpret "omniscience" and "omnipotence", and not all of them are going to be biblically relevant or logically reasonable.  I imagine that these claims represent formalized, philosophical representations of God which might not have an exact biblical basis (like I suspect the Trinity does) -- not meaning they are biblically incorrect but just not necessarily exactly correct in the way a human might understand them.  Still, I think this is a relevant question.)
In historic theology, there are three primary attributes of God, omnipotence, omniscience and omnipresence. (I have never heard of omnibenevolence until today, and while we surely could postulate many novel omni-x combinations, they would be just that novel).
Omnipotence is the lack of limitation to cause a desired effect. Omniscience is the lack of limitation on knowledge. Omnipresence is the lack of dimensional limitations.
Bear in mind that we are now dealing with infinite qualities, things which finite men cannot fully grasp - we can only meditate on them, ponder them and &quot;see things dimly&quot;:

1 Cor 13:12
12 For now we see only a reflection as in a mirror; then we shall see face to face. Now I know in part; then I shall know fully, even as I am fully known.

A common thought-puzzle raised in objection to the omnipotence of God is the question, can God create a weight he cannot lift? However, this question actually postulates a logical contradiction. There are some things God cannot do because they are, to put it plainly, nonsense. For example: God cannot act contrary to his nature; this is not a limitation of his power but a simple fact of his being. It is simply a contradiction to postulate an infinite being acting contrary to his nature; he has no such limitation that would make it possible to do so.
On to the specific difficulty posed in the question. The question fails to recognize the third of God's primary attributes, omnipresence and also misrepresents the attribute of omniscience.
God's omnipresence applies not only to space but also to time. God created time at the same point that he created space (and science also concludes that time began with the material universe, FWIW). God is outside of time; he is not temporally limited in any way. For God, all time is present - he is the great I AM.
Furthermore God's omniscience is therefore not constrained to temporal thinking; he knows everything in the present. He has no conflict with what will happen in the future, and the future does not limit him, because for him there is no future - all of existence is now.
God's choices happen in the eternal-present and in no way limit him because they are made according to his perfect and infinite nature. Whatever God does he does in this capacity and doing something other than what he has done is not within his nature because what God wills simply is. &quot;And God said, let their be light, and there was&quot;.
In essence, God quite literally defines all of reality.
Edit 2012-01-04: In response to Indigo's comment, which is a common misconception:

Obviously, if GOD is bound by the laws of logic, then one would have to explain how HE can be bound by something he HIMSELF created (or, if HE didn't, who did it then).

The mistake here is in assuming God created the &quot;laws&quot; of logic, instead of recognizing that logical coherence derives from God's nature as an inherent characteristic. In fact, our capacity for coherent logical reasoning reflects the image of God.
(Interestingly, but as something of an aside, the Bible calls the second person of the Trinity (Jesus) the &quot;Word&quot; of God, from the Greek logos, the same root as our word logic. The Word was not created, but rather &quot;proceeds&quot; from the essence of God by his nature. In other words (pun not intended) the person of Jesus is a natural consequence of the being of God, as are the persons of the Father and the Holy Spirit.)
Edit 2012-01-06: In response to Indigo's subsequent comment:

Ahh, now you make a differnece between &quot;created by God&quot; and &quot;derived from God&quot;. Yet this doesn't help with the dilemma, unless you define &quot;almighty&quot; by &quot;bound by its natures inherent characteristics&quot; or something like that. As soon as you do that, I am with you. [sic]

Any being is bound by their nature; God is by nature infinite, which is to say, unlimited. That does not mean he can act contrary to his nature; no being can - it means that anything contrary to his nature is by definition nonsensical, or as I put it in my answer, a logical contradiction. Not even God can make something be black and white at once, not because his power is &quot;limited&quot;, but because that's a contradiction in the definitions of the terms. In other words the only way that something can be black and white simultaneously is to alter the definitions of the terms or use abstractions.