If you play "Impossible Bosses" on bnet, you can see some very well constructed, WOW-like bosses - which require every player to be on their toes.
That said, making a boss isn't easy and if this is a single-player campaign you can afford to give a boss Neutral Hostile status and add abilities when it reaches % health (like others have suggested), however, abilities like blink and windwalk need good triggering/scripting otherwise the AI won't use them correctly.
Actually, the Neutral Hostile AI can be fairly stupid with some spells, so I believe you should order it to cast things (or create dummy units and have them do it) under specific conditions (the attacking player's hero gets below 20% hp? The boss should cast stormbolt on him).
Don't give the boss too much health, unless you want to see players whacking away at it for hours - make the boss smart and force its attacker to stop attacking it for a time. Alternate the experience by making him spawn creeps to distract or overwhelm the player. Wanderer's of Sorceria's Book 5-6 have fairly good bosses, as an example.