Illidan starts with 3 mana, which doesn't sound too bad... but honestly, this is the hardest mechanic about this encounter.

I found in the early game he will often fill his board with 5x 1/1[Hearthstone Card (Illidari) Not Found] hence early board clear Holy Ripple / Breath of the Infinite 
Another potential roadblock is the pesky Satyr Overseer with a weapon - you'll soon find yourself overwhelmed and nearly dead by turn 5, especially with each of his hero attacks dealing an extra 1 damage to you and your minions.

Your ideal situation is:
Early: a board clear, Penance, a dragon, Reliquary of Souls or Dragonmaw Sentinel to ensure you have a body and healing down on the board.
Mid: Your Sandhoof Waterbearer + Hefty Dragons mid-game bruisers who will keep you in shape.
Complete your quest
Late: Obelisk Plain sailing and Galakrond to clean up and supply minions.

This deck features survivability and a variety of removals so you can keep those early Priestess of Fury and Imprisoned Antaen at bay.
Turtle your way to the 10 mana mark, if you have decent health by then, the hardest part is over and the deck will stabilise the fight in your favour.

Keep your healing up not only to survive Illidan being 3 mana crystals ahead but also to contribute to your Activate the Obelisk
Heading into the 10 mana main game with good health and a completed quest will ensure some smooth sailing for the rest of the game.

By the late game, Illidan should be low on card draw/hand cards, cement his fate with Galakrond and endless priest minions.
If your extra like me, defeat him with Tyrande. Sorry not sorry.

Noteable Card Strengths
1. Galakrond, the Unspeakable is great throughout the game for extra priest minions, plus board removal.
2. Holy Ripple to deal with Command the Illidari / Coordinated Strike

Good luck and enjoy your shiny golden Kael'thas!
- Paragon