A paradox is defined as:

a statement that is apparently self-contradictory or absurd but really contains a possible truth.

In other words, it is a statement that at first seems impossible in that it contradicts itself, but upon closer examination, there is a truth to be found. In Shakespeare's Macbeth, we see this quite clearly in the theme of "fair is foul and foul is fair." Translated, this means that what is good is bad, and what is bad is good. ("Fair" means "good" and "foul" means "bad.") This theme is introduced in Act One, scene one, by the witches—and if anything in this play is foul, it all begins with the "weird sisters" (as Macbeth calls them: he even notes that while they look like women, they have beards...they are a contradiction themselves). 

Fair is foul, and foul is fair.

Hover through the fog and filthy air. (11-12)

That the witches are there to present this dark theme would have been no surprise to the Elizabethans who believed completely in ghosts, witches, the devil, elves, fairies and other supernatural creatures.

The theme is addressed by Macbeth first in scene three:

So foul and fair a day I have not seen. (39)

He is stating that the day is fair in that they have won in battle, but the weather is terrible. By looking at the theme in the context in which it is used, we find some sense in how the day can be "fair" and "foul" at the same time.

Macbeth addresses it directly when he considers the source of the good news promised by the witches: he figures being king someday has to be a good thing, but coming from servants of the devil, how is it possible that anything good could come from them?

This supernatural soliciting

Cannot be ill, cannot be good. […] (141-142)

He knows in his heart that he should not believe what the witches are telling him—nothing good can come from evil...how can he be king (a "fair" thing) when it comes from witches (a "foul" thing)?

If good, why do I yield to that suggestion

Whose horrid image doth unfix my hair

And make my seated heart knock at my ribs,

Against the use of nature? (145-148)

However, Macbeth's problem is that he lets his ambition override his good sense, and that leads to his downfall and destruction. And so, in understanding what "fair is foul...." means, the answer to the question in the witches' second set of predictions later in the play has to be "B."

"Lesser than Macbeth, but greater" means that Banquo may not be as important and powerful as Macbeth, but that he is a better man; this is evidence when Macbeth asks Banquo to "have his back" if the need should arise (as Macbeth anticipates the murder of Duncan). Banquo says he will support Macbeth as long as Macbeth does not ask him to do something that goes against his sense of right and wrong. Knowing that Banquo is "greater" in this way, Macbeth chooses to have him killed.

Additional Source:

http://www.enotes.com/macbeth/themes