A good way to add complexity in a manageable way is to implement conditions. Not ridiculous conditions that can be met immediately like "if a unit has a status" or "if your deck has no duplicates" -_- that's just silly.
I think I disagree with this -- or at least its underlying assumptions.
First, there are different kinds of complexity -- some good and some bad. I am all for what I would call "strategic complexity" -- complexity where decisions made during game play have rich implications which are challenging to analyze in light of potential opponent responses. And I totally oppose what I would describe as "rules complexity" where what a card does is tedious to describe, understand, and implement. Cards with multiple effects and/or convoluted conditions may or may not have strategic complexity -- but they ALWAYS have undesirable rules complexity.
Placing conditions on cards can be of mixed value -- regardless of the number of steps needed to meet the condition (although more steps can often mean more rules complexity). If the condition is one that can be addressed in multiple ways by both players, it is a wonderful addition.
For example, one of my favorite cards is Villentretenmerth who has the condition of destroying the highest powered unit on the battlefield after a certain time. This condition is potentially addressed by both directly addressing Villentretenmerth or by boosting/damaging other cards. The condition is trivial, but the potential interactions are rich.
On the other hand, one of my least favorite cards is Gord who boosts himself by one for every special card previously played. All this condition does is to reduce the strategic complexity by dictating certain elements of card sequencing. There is no way to interact with an opponent playing special cards -- the only real strategy is playing to have an opportunity to remove the card (last say). And then the sequencing of the tall punish card is also coriographed.