Constantinople always, Antioch in 1066 (but not 867), although they tend to expand into Egypt and the Levant fairly rapidly in both start dates.
Iconoclasm counts as a heresy in-game, and was seen as a distinct religious trend historically (with iconoclasts and icononodules clashing consistently). Heresy was honestly probably more important in Byzantine history than it was in medieval Catholicism, as the Paulicians controlled significant military forces and territory, while the Iconoclasts of course ruled the empire at various points, while most of the Western heresies were never militarily significant (it's not even clear that the Cathars actually existed as any sort of unified movement rather than as a boogie-man for excited inquisitors) until the very late period (when the Hussites show up, who aren't even in the game).