Can two different topological spaces cover each other? I.e. do there exist non-homeomorphic $X$, $Y$ and covering maps $f:X\rightarrow Y$, $g: Y\rightarrow X$?
I have a basic understanding of covering space theory as its taught in school.
I was inspired by this question Two covering spaces covering each other are equivalent?
I have done some of the things you would do, looking at what happens to fundamental groups.  And I've tried to find counter examples by drawing  graphs.
 A: The answer is yes and X and Y can even be surfaces.
Let $X_1$ be the twice punctured torus, $X_2$ the 4 punctured sphere, $Y_1$ the once punctured torus, and $Y_2$ the thrice punctured sphere.
Here is a proof that either $X_1$ and $Y_1$ mutually cover each other, or $X_2$ and $Y_2$ mutually cover each other. Note that there is a natural 2-sheeted covering from $X_1$ to $Y_1$ and likewise for $X_2$ and $Y_2$ so we only need to establish the other direction. 
Now $\pi_1(X_i) = F(3)$ and $\pi_1(Y_i) = F(2)$, where $F(n)$ is the free group on $n$ generators. Note that $F(2)$ is a natural subgroup of $F(3)$ so the correspondence between subgroups of the fundamental group and covering spaces guarantees that there is a covering space of each $X_i$ which have fundamental group $F(2)$, and since $X_i$ is a surface the covering space must also be a surface. 
It is a fairly straightforward exercise from an introductory course on the fundamental group to show that the fundamental group of a genus $g$ surface with $m$ punctures is $F(m+2g-1)$. A less obvious observation is that the fundamental group of a non-punctured surface is not free. Here is a link with quite a few proofs of this fact, most aren't that elementary unfortunately. 
This tells us that $Y_1$ and $Y_2$ are the only surfaces which have $\pi_1 = F(2)$. This means that either $Y_1$ or $Y_2$ covers $X_1$ and the same is true with $X_2$. Obviously if either $Y_1$ covers $X_1$ or $Y_2$ covers $X_2$ we are done, since they mutually cover each other and are not homeomorphic. So assume for the sake of contradiction that neither of those coverings exist. 
This implies that $Y_1$ must cover $X_2$ and $Y_2$ must cover $X_1$. But the composition of covers of $Y_1$ to $X_2$, $X_2$ to $Y_2$, and $Y_2$ to $X_1$ gives a covering map from $Y_1$ to $X_1$ which is a contradiction. 
So either the once and twice punctured tori cover each other or the 3 and 4 punctured spheres do. (My money is on the spheres, but I could be wrong).
Sadly this proof isn't strictly constructive as it only gives you 2 possible pairs of spaces. If anyone has a simpler proof, or a more constructive example (or if they can rule out one of the pair, or prove that it's both) that would be awesome.  
