Should I publish a paper if its results overlap significantly with an earlier paper?

I once wrote a paper with an undergraduate that I thought was very nice. After it was accepted for publication, we found a paper not only proving our results, but going a step further. We hadn't found it previously because, similar to your situation, they used different terminology. In our case, our proofs didn't add anything new, and our results were weaker, so we withdrew the paper before it was published. That same undergraduate went on to write more papers with me, and is currently a successful graduate student. I mention this to emphasize that not publishing is not the end of the world.

If you decide to publish, you should definitely cite the work you found, and mention to the reader that their proofs are different and came first. Something like the following should be fine: "After a preprint version of this paper was made public I was made aware of [Y], which appeared first and obtained Theorems ###. As the methods this paper are completely different, we believe that the proofs still merit publication."

It is not necessarily your job to explain those differences, unless you think it would help the reader. However, it is your job to convince (yourself, the readers, and) the referee that your paper is worthwhile. So you need to deeply understand the differences, and perhaps explicitly point out what your paper adds to the literature.

I imagine that the authors of Y mentioned their paper because they have priority, and would appreciate citations to their work. After you have cited their work, mentioning their priority, you owe no more obligations to them. (Although, if they contact you again, you can treat their communications with respect!) Don't try to mind-read their intentions. Focus on your own beliefs, whether you personally think your proofs would help readers understand the topic more deeply and give them interesting techniques. If you like, you can send Y an updated version of your paper, which clearly gives them priority, and kindly ask if they have any further comments.

In the few times in my career I have been in a similar situation, I have withdrawn my paper before publication, but gone on to modify it to be different enough from the other's (and my) prior work that it justifies publication. The lesson is: don't always view a paper as a complete, fixed, immutable work of scholarship but instead a working space, amenable to revision and improvement. Viewing your work this way may prod you to discover a new result (or a new approach to a known result) so your prior work wasn't "in vain."