This is a very good question. The same operator algebra does not imply that $H(J,h)$ and $H(h,J)$ have the same spectrum. As has been mentioned in Dominic's answer, even the ground state degeneracy is different under the interchange of $J$ and $h$ ($J\gg h$: symmetry-broken two-fold degeneracy, and $J\ll h$ unique ground state), therefore it is impossible to establish a one-to-one mapping between the eigenstates of $H(J,h)$ and $H(h,J)$. One must keep in mind that the duality transformation only preserves local dynamics but the global (topological) properties will be lost. This statement becomes sharper in higher dimensions. Like in 2D, the $\mathbb{Z}_2$ lattice gauge theory is dual to the quantum Ising model, however the topological order of the gauge theory (most prominently the topology-dependent ground state degeneracy) is completely lost in the dual Ising model, even though there is a beautiful correspondence between their local excitations (e.g. charge and vison).
Nevertheless, duality is still very useful if we only focus on the local excitations. Many important problems like low-energy dynamics, phase transitions and criticality are only related to local excitations, then the duality transformation can help us a lot in understanding these things.
To appreciate the duality in the 1D transverse field Ising model, it is better to just look locally and try to figure out the local correspondence of the bulk excitations, without caring too much about the global properties such as boundary conditions, infinite strings, ground state degeneracy etc. The idea of duality is actually simple: one can describe a 1D Ising chain either by the spin variables living on each site, or by the kink variables living on each link. A kink on the spin chain is a link across which the Ising spins are opposite. Then every link $l$ can only have two possible states:
$$\tau_l^z=\left\{\begin{array}{cc}+1 & \text{unkinked,}\\ -1 & \text{kinked,}\end{array}\right.$$
If we have specified all the kink configuration $\tau_l^z$ on each link $l$, we can actually determine the spin configuration $\sigma_i^z$ on each site $i$, with only one additional piece of knowledge about the left-most spin $\sigma_0^z$. The trick is just to accumulate the kink configurations from left all the way to the right,
$$\sigma_i^z=\sigma_0^z\prod_{0<l<i}\tau_l^z.$$
So the spin configuration is uniquely determined by the kink configuration (up to the left-most spin). If we count the number of states in the Hilbert space, the Hilbert space dimension will be $2^{N_\text{site}}$ in the spin language and $2^{N_\text{link}}$ in the kink language, where $N_\text{site}$ and $N_\text{link}$ are the number of sites and links respectively, which are equal (apart from the left-most site) on the 1D lattice, so the Hilbert space dimension is actually the same in both languages. In this sense, we can say that the correspondence between the spin and the kink descriptions is almost one-to-one (especially in the thermodynamic limit), even though there might be some complication arising from the left-most boundary (which however is to be ignored in the duality transform, as duality only cares local properties).
Now we can rephrase the original transverse field Ising model
$$H=-J\sum_{i}\sigma_i^z\sigma_{i+1}^z-h\sum_{i}\sigma_i^x,$$
in the kink language. It is not hard to see that the coupling between the Ising spins is just the chemical potential for the kink
$$-J\sum_{i}\sigma_i^z\sigma_{i+1}^z=-J\sum_l\tau_l^z,$$
which basically follows from the physical meaning of the kink variable $\tau_l^z$. Admittedly this equality may run into a little trouble on the boundary, where some sites or links might be missing, but they do not affect the local properties deep in the bulk, so we just ignore. The translation of transverse field term is more involved. In the spin language $\sigma_i^x$ operator just flips the spin on site $i$, which would correspond to simultaneous creation or annihilation two kinks on the links adjacent to that site, or moving an existed kink across the site.
In either case, flipping a spin would correspond to simultaneously changing the kink variables $\tau^z$ on adjacent links, which can be carried out by $\tau^x_l\tau^x_{l+1}$, s.t.
$$-h\sum_i\sigma_i^x=-h\sum_{l}\tau^x_l\tau^x_{l+1}.$$
Obviously the relation between $\tau^x$ and $\tau^z$ is exactly the same as our familiar $2\times 2$ Pauli matrices $\sigma^x$ and $\sigma^z$, s.t. $\tau^x|\tau^z=+1\rangle=|\tau^z=-1\rangle$ and $\tau^x|\tau^z=-1\rangle=|\tau^z=+1\rangle$, and the algebraic relations like $\{\tau^x,\tau^z\}=0$ are just consequences that follow. As the OP have pointed out, the algebraic relations can not guarantee the representation to be fundamental, it is actually the above physical picture that guarantees the representation of the kink operators.
Putting together the above results, we arrive at the Hamiltonian in terms of the kink operators $\tau_l^x$ and $\tau_l^z$
$$H=-h\sum_{l}\tau^x_l\tau^x_{l+1}-J\sum_l\tau_l^z.$$
One might have been wondering for a while that why I kept using the symbol $\tau$ instead of $\mu$ in the original post. Now it is clear that $\tau$ is still one step away from $\mu$ by a basis transformation on each link that redefines $\tau^x=\mu^z$ and $\tau^z=\mu^x$ (relabeling $x\leftrightarrow z$). Such a unitary transform will not change any physics, but just to bring back the standard form of the transverse field Ising model to accomplish the duality transform,
$$H=-h\sum_{l}\mu^z_l\mu^z_{l+1}-J\sum_l\mu_l^x.$$
So the duality between $J$ and $h$ is now manifest, but what is the physical meaning of $\mu_l^z$ indeed? To answer this question, one should first understand that the relation between $\tau^z$ and $\tau^x$ is just like that between the coordinate and the momentum. They are related by a $\mathbb{Z}_2$ version of the Fourier transformation. If we treat the two states of $|\tau^z=\pm 1\rangle$ as two position eigenstates in a two-site system, then the $\tau^x$ eigenstates $|\tau^z=+1\rangle\pm|\tau^z=-1\rangle$ are nothing but the momentum eigenstates with the momentum = $0$ and $\pi$ respectively. In this sense, we can say $\mu_l^z\equiv\tau_l^x$ is the conjugate momentum of the kink variable $\tau_l^z$ on each link. In fact, this concept is so important that people invent a name for $\mu^z$, i.e. the vison variable, s.t.
$$\mu_l^z=\left\{\begin{array}{cc}+1 & \text{vison off,}\\ -1 & \text{vison on.}\end{array}\right.$$
By saying that the vison is the conjugate momentum of the kink, we mean that if there is a vison sitting on a link then the kinked and the unkinked configurations across that link will be differed by a minus sign in the wave function. Unlike the kink which is just another way to encode the spin configuration, the vison does not have a correspondent spin configuration. In fact, the vison configuration is encoded in the relative sign between different spin configurations in the wave function. It represents the inter-relation among the spin configurations other than any particular spin configuration itself, or in other words, the quantum entanglement in the spin wave function.
Mathematically this can be seen from the fact that the vison operator $\mu_l^z$ is non-local in terms of the spin operator
$$\mu_l^z=\prod_{i<l}\sigma_i^x=\tau_l^x,$$
which flips all the spins to its left to create (or annihilate) a kink. Now let us discuss more about this infinite string of $\sigma^x$ stretching all the way to the left. A first question is that can we "gauge" this string to right? This can be done by applying the operator $S\equiv\prod_i\sigma_i^x$, as
$$\mu_l^z\to S\mu_l^z= \prod_{i}\sigma_i^x\prod_{i<l}\sigma_i^x = \prod_{i>l}\sigma_i^x.$$
One can see the operator $S$ simply flips all the spins in the system, meaning that it actually implement the global Ising symmetry transformation to the spins $\sigma_i^z\to-\sigma_i^z$. Because $S$ is a symmetry of the Hamiltonian (as $[S,H]=0$), the eigenstates of $H$ are spitted into the even ($S=+1$) and the odd ($S=-1$) sectors. In the even sector, we can gauge the string to the right; while in the odd sector, gauging the string to the right will induce a $\mathbb{Z}_2$ gauge transformation of the vison $\mu_l^z\to-\mu_l^z$. So combined with the gauge transformation of the vison, the vison string can be made invisible indeed. Then what is the significance of the this vison string? Recall that $\mu_l^z=\tau_l^x$ is also the creation/annihilation operator of the the kink. So applying a string of $\sigma^x$ operators will actually create two kinks at both ends of the string
$$\tau_{l_1}^x\tau_{l_2}^x=\prod_{l_1<i<l_2}\sigma_i^x.$$
The kink is a local excitation of the system (in the $J>h$ phase), so it can be viewed as a particle. From this perspective, we can see emergent particles at the ends of the string, which is exactly one of the central theme of Levin-Wen model and string-net condensation.
In fact, there is a very interesting relation between the 1D transverse field Ising model and the 2D Levin-Wen model (with $\mathbb{Z}_2$ topological order), that the former can be considered as a synthetic dislocation of the latter by anyon condensation, which was described in a paper (arXiv:1208.4109) that I wrote with my friend Chao-Ming and Prof. Wen. We basically showed that the 1D transverse field Ising model can emerge in the 2D $\mathbb{Z}_2$ topological ordered system as some kind of line defect, where some particular type of the strings between the anyons in 2D will naturally degrade to the vison strings along the emergent 1D Ising chain. So in this sense, the invisible string in the Ising model is really the same invisible string in the string-net condensate (but just confined to the 1D system).
Best Answer
I don't see how you get mixed terms. Your $U$ acts on every other site. For instance (as operators acting on different sites commute) $$\ldots+ U \sigma^{2i}_x \sigma^{2i+1}_x U^{-1} +\ldots= \ldots \sigma^{2i}_z \sigma^{2i}_x \sigma^{2i}_z \sigma^{2i+1}_x \ldots=\ldots i \sigma^{2i}_y \sigma^{2i}_z \sigma^{2i+1}_x \ldots=\ldots-\sigma^{2i}_x \sigma^{2i+1}_x\ldots,$$ and similarly for the Pauli $y$-matrices.
EDIT: Maybe you made a mistake multiplying the Pauli matrices? Here is the full multiplication table for the Pauli matrices: http://www.its.caltech.edu/~hmabuchi/Ph125b/HW7-solutions.pdf
$J$ can be omitted because it is not zero compared to $\Delta$ and you can divide (rescale) the Hamiltonian by $J$ and absorb it into $\Delta/J \rightarrow \Delta'$. If $\Delta \rightarrow \infty$ then you just recover the Ising model. Remember, this transformation is unitary, which means it's just a change of basis in Hilbert space. It can't change anything "physically" and that tells us that it's only the relative $\pm$ - sign between $J$ and $\Delta$ that is physical.