Hmm.. Or just have the big guy have insanely high dex. Players flanking --> Denied dex.
An important houserule of mine - enemy is flat-footed when you make an AoO against him.
I assume that #1 suggestion will be a high Dex enemy with high dodge bonuses, because they're not added when flat-footed.
The enemy is supposed to fight melee, but spells for buffing or defense are allowed.
He's going up against a 20th level PC.