What is the most expressive logic such that presentations of algebraic structures "work"? I feel like this is one of the best questions I've asked in a while. Hope you enjoy it.
In my opinion, one of the most important ideas in modern algebra is the idea that we can present algebraic structures by generators and relations. Explicitly:


*

*Start with a theory $T$ and a set $X.$

*Write $F(X)$ for the $T$-algebra freely generated by $X$.

*Let $R$ denote a binary relation on $F(X)$

*Let $R^\sim$ denote the least $T$-algebra congruence on $F(X)$ that includes $R$.

*We define that $\langle X \mid R \rangle$ is just $F(X)/R^\sim.$
Now if $T$ is an algebraic theory (by which I mean that it is axiomatizable purely by universally quantified equations), then we can certainly carry out all of the above steps. But really, this is far too restrictive; if $T$ is an algebraic theory, then:


*

*we can take Cartesian products of $T$-algebras, and

*every subset of a $T$-algebra $X$ that is closed under the operations of $T$ is itself a $T$-algebra under the induced operations.
and neither of these observations was used to ensure that presentations are well-defined. All we really needed was:


*

*Free algebras exist.

*For binary relation $R$ on $F(X)$, there is a least congruence relation on $R^\sim$ that includes $R$.

*Congruence relations on a $T$-algebra and quotients of that algebra are essentially the same thing.
This motivates my question.

Question. What is the most expressive logic such that presentations of algebraic structures "work"? Alternatively, what is the most expressive logic such that each of the above three requirements is satisfied?

 A: This is not an attempt of full answer but is too long for a comment.
While reading Gorbunov's "Algebraic theory of quasivarieties" (in Russian) I've stumbled upon the following construction. In my opinion, it is interesting and similar to yours, but instead of binary relation we have the set of formulas as the set of relations. I don't know if you are familiar with this construction or not and can it be helpful to proceed in answering exactly your question, so I will delete my answer if it is not. 
This method of describing $L$-structures was proposed by Maltsev. I am not sure about the terminology below since it is my translation from Russian but the construction is clear.
Let $L$ be a signature and $\bf K$ be a class of $L$-structures, $\mathcal{A} \in \bf K$. Consider the set of variables $X$ and the set $\Delta$ of atomic $L$-formulas with variables from $X$. 
We will say that $(X, \Delta)$ defines $\mathcal{A}$ in $\bf K$, if there exists $f \colon X \to A$ satisfying:


*

*$f(X)$ generates $\mathcal{A}$ and $\mathcal{A} \models \Delta$ in the interpretation $f$.

*For all $\mathcal{B} \in \bf K$ and $g \colon X \to B$, if $\mathcal{B} \models \Delta$ in the interpretation $g$ then there exists a homomorphism $h \colon \mathcal{A} \to \mathcal{B}$ such that $h(f(x)) = g(x)$ for all $x \in X$.


If $(X, \Delta)$ defines $\mathcal{A}$ with $f$ and $\mathcal{B}$ with $g$ in $\bf K$, then a homomorphism $h \colon \mathcal{A} \to \mathcal{B}$, such that $h(f(x)) = g(x)$ for all $x \in X$ is an isomorphism. Hence an $L$-structure defined by $(X, \Delta)$ is unique up to isomorphism. 
If this $L$-structure exists we denote it by $\mathcal{F}_{\bf K}(X, \Delta)$. $X$ is said to be the set of generators and $\Delta$ is said to be the set of relations of $\mathcal{F}_{\bf K}(X, \Delta)$.
An abstract class $\bf K$ of $L$-structures is called a prevariety if $\bf{K}$ $= \bf{SP}$$($$\bf{K}$$)$.
There is an existence theorem proven by Maltsev.
Theorem: An abstract class $\bf K$ of $L$-structures is a prevariety if and only if $\mathcal{F}_{\bf K}(X, \Delta)$ exists for every defining pair $(X, \Delta)$.
This theorem describes precisely those classes of $L$-structures in which this method of presentation by generators and relations "works". I hope this will be helpful or at least interesting for you.
