Order of authors in a paper

Rule #1: Always try to pin these types of things down before performing the work.

Rule #2: Understand that academia (graduate school) is run on an implicit pecking order:

Departmental pressures and requirements > Advisor > PhD Student > Master's Student

This makes complying to Rule #1 very difficult in practice. Every early career researcher runs into the issue you have described in some form. (Not that this makes such practices right). People higher than you in the pecking order will use administrative leverage to get what they want.

Advisor: "I am the first author on this paper." (And if you disagree, you'll have to find a new advisor and lose a year's worth of work).

Department: "Give Professor Smith what she wants or we will not sign off on your degree."

PhD Student: "Collect this data for me. (And then try to convince someone that you actually did the work and not me)."

The order of attribution should be based on the order of contribution in most CS-based fields. Equal contributions are noted by alphabetical order of the authors' surnames, sometimes with a footnote indicating equal contribution.

I would bring the issue up first with the PhD student directly. I would then speak with his/her advisor. The advisor is essentially the court of last resort. An advisor also will be able to help with the navigation of what actually constitutes authorship for each party. At the very least, your own advisor should (hopefully) be able to help you obtain credit for your work in the form of a chapter in your thesis or something.

Going forward, I would be firm in establishing what the authorship expectations will be on any work you do. You will at times be forced to balance fairness in authorship and expediency in obtaining your degree.

I will note that I take the pecking order things into account when I interview applicants for a job. I care much less about author order and much more about what the person actually did for the paper. Thus, if the OP applied to a job with me, I would likely give his research the same weight whether he was first or second author. I fully understand that superiors sometimes take advantage of their underlings.

My answer to all three of your questions: Don't bother too much. Often such short-term unfair situations will level out.

Next year you start your PhD and write a second paper with the same co-author. And then time you will be the first author and profit a lot from the experience of your co-author. Or someone leaves academia, you have to take over and just by adding the finishing touches, you get a great paper. Or you supervise a brilliant masters student winning you another easy paper. Or an office mate thanks you for your thoughtful coffee break discussion by adding you to his latest paper.

Sometimes (this time) you lose, sometimes (maybe next time) you win.

You have to find out and be aware of the authors wanting to trick their co-authors.

Best practice depends on the particular (sub-)field. Look at how it is in yours. Also, rules are flexible.

In mine, the AMS guidelines are usually the norm: alphabetical family name ascending lexicographic order, regardless of authors' individual contributions.

In any case, you may explicitly state contribution in a footnote.

Other comments stress clearly enough the importance of making things clear ahead of writing. I would just add that your own contributions will speak for themselves regardless of the order in which you appear as an author (as long as you do!).