When does an FO property kill off NL-hardness? Context:  We consider only digraphs.  Let CYCLE be the language of graphs with a cycle; it is an NL-complete problem.  Let HASEDGE be the language of graphs with at least one edge. Then trivially, $\text{CYCLE} \cup \text{HASEDGE}$ is no longer NL-hard, while $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ stays so.

Actual problem: I'm wondering if the language $$\text{CYCLE} \cup \{(V, E):(\exists u,v,x,y)[E(u, v) \land E(x, y) \land \neg E(u, y) \land \neg E(x, v)]\}$$ is still NL-hard.

Question: For which FO formula $\phi$ on the vocabulary of graphs is
$$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$$
NL-hard?  Is this property decidable?

Thanks for your input!
Let me call the property in your "Actual Problem" $\text{NODIAG}$. The following mapping reduces $\text{CYCLE}$ to $\text{CYCLE} \cup \text{NODIAG}$: 

For a given $G=(V,E)$, replace every vertex $v$ in $G$ by two copies $v$ and $v&#39;$, and if there is an edge $(u,v)$ in $E$, let $G&#39;$ have edges $(u,v), (u,v&#39;), (u&#39;,v)$ and $(u&#39;,v&#39;)$. 
Thus for every $G$ the graph $G&#39;$ satisfies $\neg \text{NODIAG}$. 

Moreover, $G&#39;$ has a cycle iff $G$ has a cycle, therefore $G&#39;$ satisfies $\text{CYCLE} \cup \text{NODIAG}$ iff $G$ satifies $\text{CYCLE}$. Therefore $\text{CYCLE}\cup \text{NODIAG}$ is NL-hard. 

I think a similar construction would work for every purely universal property.