[Edited mostly to include the second example, corresponding to
$(t,X) = (3,-115/126)$]
Thanks to Jordan Ellenberg for
calling attention to this nice question on his blog.
I didn't remember an example in my "private archive", but the question
is close enough to some of my previous computations that I was able to
adapt those techniques here. It turns out that there are infinitely many
such pairs (even up to quadratic twist); one example has both torsion
subgroups defined over the 7th cyclotomic field ${\bf Q}(\zeta_7)$:
the curve with coefficients $[0,-1,1,-2,-1]$, i.e.
$y^2 + y = x^3 - x^2 - 2x - 1$,
of conductor $147 = 3 \cdot 7^2$ and discriminant $-147$,
and the curve with coefficients
$$
[0,-1,1,-1424883795842044404862,-20702237422068075268318817670099],
$$
conductor $8480886141 = 3 \cdot 7^2 \cdot 13 \cdot 251 \cdot 17681$,
and discriminant $3 \cdot 7^2 13^{13} 251^{13} 17681$.
This felt familiar, and it turns out that I had already encountered
the quadratic twists of these curves by ${\bf Q}(\sqrt{-7})$
because one of them, also of conductor $3 \cdot 7^2$ but
discriminant $-3 \cdot 7^8$, is the Jacobian of the Shimura
modular curve computed in my paper
Elkies, N.D.: Shimura Curves for Level-3 Subgroups of the $(2,3,7)$
Triangle Group, and Some Other Examples,
Lecture Notes in Computer Science 4076
(proceedings of ANTS-7, 2006; F.Hess, S.Pauli, and M.Pohst, ed.),
302$-$316;
arXiv:math/0409020.
(so it was already in my "public archive"...). See page 11 of
the arXiv version:
Mark Watkins noted that this curve 147-B1(I) actually has 13-torsion
over the cubic field ${\bf Q}(\zeta_7^{\phantom1} + \zeta_7^{-1})$;
I then explained this observation from the Shimura-curve structure,
and noted (footnote 5) that the twist of $X_1(13)$ parametrizing
curves over ${\bf Q}$ with a $13$-torsion point over
${\bf Q}(\zeta_7^{\phantom1} + \zeta_7^{-1})$
has at least one more orbit of rational points, which yields
the curve of conductor $8480886141$.
As Jordan observes in his blog, and also in his comment here,
the question of finding pairs of curves with "the same" cyclic
$13$-isogeny is equivalent to finding rational points
(away from some degeneracy locus) on a certain surface $S$.
This surface turns out to be "honestly elliptic" of the simplest kind
(with $\chi=3$): the canonical class $K_S$ is positive but not ample,
with a two-dimensional space of sections that gives a map
$S \rightarrow {\bf P}^1$ whose fibers are curves of genus $1$.
This fibration has sections defined over ${\bf Q(i)}$ but not over ${\bf Q}$.
But many of the first few fibers have rational points small enough
to find by a brief computer search. Any one such point yields
infinitely many rational points on its fiber, and thus infinitely
many pairs of $j$-invariants of elliptic curves with Galois-isomorphic
subgroups of order $13$.
The surface has a birational model
$
Y^2 = (X^2+4) A(X),
$
where $A(X)$ is the quadratic $A_2 X^2 + A_1 X + A_0$
whose coefficients $A_2,A_1,A_0$ are the following sextics in $t$:
$$
A_2(t) = t^6-4t^5+6t^4-2t^3+t^2-2t+1,
$$ $$
A_1(t) = -6t^5+26t^4-22t^3-4t^2+6t,
$$ $$
A_0(t) = 4t^6-8t^5+37t^4-74t^3+57t^2-16t+4.
$$
Thus we have for each $t$ a curve of genus $1$, though without
an obvious rational point (except for the degenerate $t=0,1,\infty$
where every $X$ makes $(X^2+4) (A_2(t) X^2 + A_1(t) X + A_0)$ a square
but the resulting elliptic curves $E,E'$ are isomorphic).
So I tried a few small values of $t$ with
Stahlke and Stoll's program ratpoints.
For $t=2$ the program reported an obstruction, and indeed
there's no $11$-adic solution. Hence our elliptic fibration
has no section over ${\bf Q}$ (else we could specialize it at $t=2$),
though there are certainly sections over ${\bf Q}(i)$, namely $X=\pm 2i$
(and also the roots of $A(X)$).
Still we can look for rational points on individual fibers,
and we already succeed for $t=3$, finding a rational solution
at $X=-115/126$, and several solutions of larger height for
other small $t$. An hour's exhaustive search up to height $50$ for $t_0$
and $500$ for $X$ finds three further solutions, including
$(t,X) = (33/17,0)$ which leads to the curves of conductor
$147$ and $8480886141$ exhibited above. The solution
$(t,X) = (3,-115/126)$ corresponds to the curves
$$
[1, 1, 0, -2193228435814, -4048327365374399852],
$$
with conductor
$133333589432694 = 2 \cdot 3 \cdot 7 \cdot 181^2 \cdot 263 \cdot 607^2$,
and
$$
[1, 1, 0, -9358273692452696799, -11018986378569871927950945915],
$$
with conductor
$N = 18612166837338258 = 2 \cdot 3 \cdot 79 \cdot 181^2 \cdot 607^2 \cdot 3253$
(these curves were recovered from their $j$-invariants using J.Cremona's
conductor-minimizing Sage routine EllipticCurve_from_j);
both curves have $x$-coordinates in the same cubic field of discriminant
$181^2 607^2$, and $y$-coordinates in the quadratic extension
of that field by $\sqrt{-181 \cdot 607}$.
Details of the computation of the surface etc. coming soon
(but probably in a separate answer because this is already
quite long or a Mathoverflow answer...).
