For ingame purposes, trace is fine. Synchronize is better ingame because most foes will have less than worthy abilities, and the outside of battle nature sync is also useful. In competitive trace is more sought after because of HAs that increase the likelihood of encountering a good ability. You'll see what I mean if you look at Gardevoir's recommended movesets prior to Gen 6.
Mega Gardevoir changes everything. You must have trace on Mega Gardevoir, unless you want the outside affect of synchronize. Otherwise synchronize and telepathy are useless.
So if you're using Mega Gardevoir, just keep trace. If not then Synchronize is better for clearing your playthrough, but trace is also ample ability power. TBH Gardevoir is good enough ingame to not have an ability.