I was asked this after Wembley and got this from somewhere on the official site:
In July 1726 there was a fair on Southernhay in which the Siege of Troy was enacted, and for some not entirely stupid reason, the inhabitants of St Sidwell's (outside the city walls) identified themselves with the attacking Greeks, or Grecians. By 1737 there was already a tradition of football matches between the city dwellers who called themselves the Blues and "the rugged inhabitants of St Sidwell's", who called themselves the Greeks.
A century later "Greeks" had given way to "Grecians". Residents of St Sidwell's described themselves as Grecians in letters to the local paper and the term was familiar in local parlance. Obviously it was never going to loom as large in the national consciousness as "c*ckney", "brummie" or "scouser", but for generations who lived in or around Exeter, "Grecian" instantly identified a St Sidwell's resident.
By extension, it was not at all surprising that the football ground just off the end of Sidwell Street should acquire a "Grecian Gate". And when the team who played there, St Sidwell's Old Boys, changed its name to Exeter City, it must have seemed almost natural that it would be given the nickname "Grecians."
Everything is entirely logical if you know the local history; without that knowledge, of course, it is a mystery defying explanation, which is why most soccer reference books either decline to explain "Grecians" or guess wrongly about the derivation.