This is an extremely general question, so I'm going to use fields as a specific example and hopefully work from there. Keep in mind, though, that a similar "re-encoding" process can be performed for just about anything which is suitably algebra/structure-like: topological spaces, lattices, relational algebras, logics, even languages.
Note: In this context $2\times F=\{0,1\}\times F=F\sqcup F=\cdots$
Let $\mathcal{F}=\langle F,+,\cdot\rangle$ be a field.
Let $Cd(\mathcal{F})=\langle 2\times F,*\rangle$, where $*:(2\times F)^2\to2\times F$ is defined as follows:
$$x*y=\begin{cases}(0,x_2+y_2)&x_1=y_1=0\\(0,x_2\cdot y_2)&x_1\ne y_1\\(1,x_2\cdot y_2)&x_1=y_1=1\end{cases}$$
Observe that $Cd(\mathcal{F})$ satisfies the following axioms:
Associativity: $$x_1=y_1=z_1\implies x*(y*z)=(x*y)*z$$
Commutativity: $$x*y=y*x$$
Distributivity: $$x_1=1\land y_1=z_1=0\implies x*(y*z)=(x*y)*(x*z)$$
Identity: $$x_1=i\implies x*e^i=e^i*x=x\quad:\quad i=1,2$$
Inverse: $$x_1=i\implies x*\overline{x}=\overline{x}*x=e^i\quad:\quad x\ne(1,0)$$
Clearly, $\mathcal{F}\ne Cd(\mathcal{F})$, nor is $\mathcal{F}$ isomorphic to $Cd(\mathcal{F})$; $Cd(\mathcal{F})$ is not even a field! Yet $Cd(\mathcal{F})$ is similar to $\mathcal{F}$ in extremely obvious ways, to the extent that $\mathcal{F}$ and $Cd(\mathcal{F})$ are "basically the same thing," or, at the very least, $\mathcal{F}$ and $Cd(\mathcal{F})$ "encode" the same thing.
Of course, without clarification, any two things can be likened to one another, regardless of how disimilar they actually are. One could easily say that a group is "basically the same" as a Lie algebra and proceed to justify why this is the case - but such an arbitrary comparison is intuitively less reasonable than that made above.
Since there are clearly "reasonable" and "unreasonable" comparisons, there ought to be a way to distinguish between them. This leads me to my question: how can I formalise the notion of "sameness"? Is it possible to define a single "sameness" relation, or are there distinct classes of "sameness"?
Update:
The notion which I am trying to capture is that $A$ and $B$ are the "same" if $A$ can encode $B$ and $B$ can encode $A$. The relation in question ranges over [classes of] structures, theories, categories, or languages (provided that "language" comes with rewrite rules and/or semantics); these can be used almost interchangeably because for any structure, there is a "theory of that structure" (up to isomorphism), for any theory, there is a "category of that theory," etc.
After doing some reading, I can confidently say that "sameness," as presented in the example, is distinct from polynomial equivalence, term equivalence, and isotopy. This is because each of these relations apply only to algebras over the same set/universe. Even extending these notions to "polynomial/term isomorphism" - if that's a thing - does not account for the differences between $\mathcal{F}$ and $Cd(\mathcal{F})$ because any map between $F$ and $2\times F$ which would be suitably "isomorphism-like" would have to send each element of $F$ to two elements in $2\times F$. It might be possible to bijectively map $n$-tuples of elements and operations of $\mathcal{F}$ to those of $Cd(\mathcal{F})$ in a way that preserves the algebraic properties of $\mathcal{F}$.
At this point, I think it would be helpful to try and create a hierarchy (or partial order) of equivalence relations ordered by logical implication. My "sameness" relation ought to be "that thing just above 'term-isomorphism'." This seems like a more fruitful approach, since it would both clarify the particular relation I am talking about while and shine a light on the connection with other, "nearby" relations (like term-equivalence).
It seems (bi-)interpretability might be of interest.
An interpretation of one structure $\mathcal{A}$ in another structure $\mathcal{B}$ is intuitively a "construction" inside $\mathcal{B}$ of an isomorphic copy of $\mathcal{A}$. Formally, it consists of a formula $\varphi$, a formula $\eta$, and a formulas $\pi_s$ for each symbol in the language of $\mathcal{A}$ such that:
$\varphi$ has some arity $n$, $\eta$ has arity $2n$, and $\eta^\mathcal{B}$ is an equivalence relation on $\varphi^\mathcal{B}$ (we think of "$\varphi/\eta$" as being the domain of our copy of $\mathcal{A}$).
If $s$ is a relation symbol of arity $k$, then $\pi_s$ has arity $nk$ and "is a well-defined relation on $\varphi/\eta$" in the obvious sense.
If $s$ is a function symbol of arity $k$, then $\pi_s$ has arity $n(k+1)$ and "is a well-defined function on $\varphi/\eta$" in the obvious sense.
The number $n$ can be thought of as measuring "relative dimension" - e.g. forgetful functors (when appropriate) yield interpretations with $n=1$, while the definition of complex numbers as ordered pairs of real numbers amounts to an interpretation of $(\mathbb{C};+,\times)$ in $(\mathbb{R};+,\times)$ with $n=2$.
Now a bi-interpretation is more than just a pair of interpretations in each direction; we also demand definable isomorphisms. Intuitively, a bi-interpretation between $\mathcal{A}$ and $\mathcal{B}$ consists of interpretations $j$ of $\mathcal{A}$ into $\mathcal{B}$ and $h$ of $\mathcal{B}$ into $\mathcal{A}$ such that there is an $\mathcal{A}$-definable isomorphism between $\mathcal{A}$ and "$(h\circ j)(\mathcal{A})$" - that is, ($\mathcal{A}$'s copy of $\mathcal{B}$)'s copy of $\mathcal{A}$ - and similarly for $\mathcal{B}$. The exact definition is a bit messy, but not surprising.
Note that (bi-)interpretations are logic-dependent: change the logic being used (FOL, $\mathcal{L}_{\omega_1,\omega}$, SOL, ...) and you change what things are interpretable in what. For example, the interpretations arising from "computable infinitary logic" play an important role in computable structure theory.