I don't believe it's possible to evade sneeze, but if it is, it's best to equip Locke with a things that boost evasion. Give him Illumina, the Paladin Shield, and anything else that gives a few points of evasion bonuses.

Or, just go all out, get a super fast character with a ton of fighting power, like Terra with Illumina, the Atma Weapon, Offering and Genji Glove, and pray that you can kill it before it lands sneeze.