How to respond to a perceived unfair editorial decision?
That is a frustrating experience that many (all?) of us were forced to endure at some point in our careers.

Fact is, a "major revision" is not guaranteed acceptance upon receive. Papers that are not rejected in the first round of review usually are close enough that they can be accepted after revision(s), but that is in no way guaranteed.

Now, in your case, the reviewer made promising remarks for the future, yet failed to act on them. It can be that they misjudged the first time, that they are inexperienced (perhaps the review was delegated to a student), that they had malicious intents, etc. This line of reasoning, however, is a dark rabbit hole best avoided. You have no way of knowing for certain what was up with the reviewer at the time and little benefit even if you did, so it's best to let that go.

The next point is the editor's decision, "decline and resubmit". Again, there is zero guarantee that the paper will be accepted by a potentially different set of reviewers. Usually, journals prohibit submitting the same paper again once it has been rejected. So, if it is a particularly important venue, I'd consider this a better thing than straight out decline. Another important point is that (at least in my field) for a resubmit after decline, a predefined amount of time is required to pass, e.g. 6 months, and a significant rewrite is expected. Practically, close enough to a new paper. If similar practices apply, it is probably easier to resubmit somewhere else.

Appealing rarely works without substantial proof of malpractice during review. In fact, you may have already gotten the best result an appeal can get you: the right to resubmit for a new set of reviewers.

Bottom line, the lost time and the additional time it will take to resubmit is unrecoverable. You have the review feedback as it is, and you have your current and previous draft. If you feel that the reviewer's directions were misplaced, you can polish up the older draft and resubmit. My advice would be to try to get the best out of both versions, take into account any remarks the reviewers had, do a thorough proofread of the paper, and resubmit at some other venue.