In OP's context, everything is either simple or complex, and for any given thing, either it's obvious which applies, or the appearance is deceptive.
Things that both appear to be, and really are, simple are hardly worth mentioning. Nor is it normally worth saying that something which appears complex really is complex. So the only cases worth mentioning are things that look simple but are actually complex, and things that look complex but are actually simple.
As others have noted, the first case is often called deceptively simple. We often admire things which are superficially simple, but which we know are actually complex, so it's effectively a complimentary expression - which once given is often followed by an explanation/discussion of the "hidden" complexity.
But we don't admire complexity for it's own sake - quite the reverse, in fact. If you're giving a value judgement on something meeting that criterion, you'd probably say something more scathing than deceptively complex - which barely exists by comparison with the "standard" version (I think people avoid the inversion partly because it might be misconstrued as a compliment).
In practice the context where we need to say something is simpler than it appears is often when we're speaking to someone else who is confused by the superficial complexity. In which case we reassure them by saying something like "It's easy, really". And then proceed to explain it.
Just because there are four positions in the "truth table" under discussion, doesn't mean we need a "matching set" of four names. Two are just trivial. The other two normally arise in different contexts (though in both cases it's likely you'll carry on by actually explaining whatever it is).
EDIT: The nearest "real-world" antonym I can think of to something that's deceptively simple is emergent complexity, a term often used of systems wherein a small number of simple elements are repeatedly recombined to create something complex. Particle physics, fractal designs, or living organisms, for example.
One phrase I've heard is deceptively simple, although there seems to be some debate about whether that refers to something that seems simple (but is in fact complex), or something that seems complex, but is really rather simple.
Six years ago, an online group debated this very phrase, and never really reached a consensus. You can read their debate by clicking on the link, but I think one contributor summed it up best by saying:
it's one of those phrases that can mean two opposite things, depending on context
The Free Dictionary has an interesting usage note on this deceptively complex word pairing; it shows that even experts disagree on the matter. Another blogger has warned, don't use this phrase in a vacuum; it won't be clear what you're trying to convey.
Sometimes, though, the intended meaning can be easily inferred from the context:
Golf is deceptively simple, endlessly complicated. (Arnold Palmer)
I'd say this question is deceptively simple, too – but I'll leave it up to you to figure out what I mean by that.
Best Answer
How about 'snowballing complexity'.