When does an FO property kill off NL-hardness?
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.