Six months and no one is willing to take a crack at this!?!The answer:
God makes God's rules.
There are two kinds of limiations on God. One comes from God's nature. Of course, since we are infinitely incapable of understanding God's nature, we're walking on thin ice when we talk about the limitations that God's incomprehensible nature places on God. But, since our relationship with God gives us some insight into God's nature, let's go with it.
My favorite analogy for God is "the source of reality." I would say that God cannot lie because anything God says becomes true. If God says, "the sky is yellow," the sky will be yellow. The speech or logos of God creates reality rather than describing it.
For the logicians out there, you can get to these "limitations" with a contrapositive.
If it lies, it is not God (If A, then not B)
If it is God, it does not lie (If B, then not A)
Of course, the legitimacy of these "limitations" on God depend on the extent to which our analogical concepts of God represent some reality. There is currently a debate among Christian theologians about whether God can suffer, because people are developing new analogies for God that lead to different conclusions about God's nature.
The second class of limitations on God are directly self-imposed. Can God change the speed of light? Sure, but such a change would throw off all sorts of other constants and physical characteristics through the universe. Presumably, if God wanted a radically different physical universe, the speed of light would already have been changed to whatever God wanted it to be.
The question about whether God can create a stone so heavy even he can't lift it is a story problem, not a philosophical paradox.