I use the braket notation where $\vert\cdot\rangle$ is a column vector and $\langle\cdot\vert$ is a row vector. Consider a square matrix given as
$$A = \sum_{ij}A_{ij}\vert i\rangle\langle j\vert$$
The transpose of $A$ is given by $A^T = \sum_{ij}A_{ij}\vert j\rangle\langle i\vert$
Define a new orthonormal basis with basis elements $\{\vert\tilde{i}\rangle\}$. I could transpose $A$ with respect to the tilde basis and obtain
$$A^{\tilde{T}} = \sum_{\tilde{i}\tilde{j}}\langle\tilde{i}\vert A\vert\tilde{j}\rangle \vert \tilde{j}\rangle\langle \tilde{i}\vert$$
In my problem, I am considering a Hermitian matrix $A$. We have $(A^T)^{\tilde{T}}$ and compare it to $A$. Obviously, if $\tilde{T} = T$, then transposing twice returns me to the original matrix $A$. However, for arbitrary choice of the tilde basis, is there anything that can be said about the relationship between $(A^T)^{\tilde{T}}$ and $A$?
Assuming you're in a real vector space. For complex vector spaces you want to talk about the conjugate transpose instead.
Transposing is independent of coordinates. The transpose of an operator $A$ is the unique operator $A^T$ such that $$ \langle x|A|y\rangle = \langle y|A^T|x\rangle $$ for all $|x\rangle$ and $|y\rangle$ (you can check that this is true with your formulas, but your formulas are not how it ought to be defined). You do not take the transpose "in a coordinate system". You just take the transpose, and after that, you may check what the entries of the transposed operator is in any given basis. This is how your formulas came to be.
Transposing twice always takes you back to the operator you started with.