First of all, nothing in Chapter 1 suggests that these steps (and their order) is the official and required way to handle things. The presentation is much more “here is a convenient way to keep track of all the decisions you have to make and a good way to make sure you’re considering each choice with the relevant information of previous choices.” It doesn’t say you have to do it this way. There also isn’t really any suggestion that there’s any kind of “timing” involved in this—you don’t have a character before, you have a complete character after, but in between everything, even steps you have “completed,” still seem fluid, to me.

But we’ll assume for the sake of the question that someone is applying this as a strict rule.

“Choose your race” does not inherently mean “apply all the effects of that race to your character.” You have made a choice, but any effects of that choice aren’t necessarily handled immediately. In particular, it explicitly mentions the ability score bonuses of your race as being something that don’t apply until later:

Your race also increases one or more of your ability scores, which you determine in step 3. Note these increases and remember to apply them later.

^{(Player’s Handbook pg. 11)}

So the fact that “Choose your race” is step 1 doesn’t necessarily mean that you have to also choose things about your racial features. The only things it explicitly discusses the timing of are the selection of your race and subrace—which happen in step 1—and applying the race’s increases to your ability scores—which happens in step 3. No other part of the process has strict, official timing. Notably, for those races that allow you to choose among various ability score increases—which is all of them, under Tasha’s—there’s nothing saying when you have to make those choices between step 1 and step 3 (in order to apply them you have to choose them so you’d have to by step 3 but even that much is left implicit).

This doesn’t necessarily mean that you choose your racial feat, say, after choosing your class—it means the official rules don’t really pin down the timing and it’s left ambiguous. But the way ability scores are handled—where you’re instructed merely to “write them down and remember to apply them later”—suggests that it’s normal and expected that not everything about your race is going to happen literally in step 1. The phrasing does not suggest this is a special exception. And the discussion of racial features is fairly similar: they discuss abilities that your final character is going to have—once you finalize them.

In short, any DM who insists on a strict order here, and then decides that you must choose your feat before your class, is basically just making that up. Rule 0 lets them do that, but otherwise the official rules really don’t back them up in those rulings. But arguably a DM who lets you choose your feat later is also just making up a ruling, because the rules don’t really say one way or the other—they just kind of heavily suggest (to me anyway) that this is the way one should rule.

Finally, I’d note that once chosen, Telekinetic is an ability that you have, continuously. It doesn’t say “When you first gain this feat, if you have mage hand already,” it just says “If you have mage hand already,” which I read as synonymous with “If you have mage hand from somewhere else.” In other words, even if your 1st-level class doesn’t provide mage hand, if you ever get it from anywhere else, I’d apply the range increase. This is a bit more reading between the lines than the above, but it is very consistent with how D&D has always worked, and I think it’s the right choice. It’s almost certainly the best choice from a perspective seeking balance or the most enjoyable gaming experience for the table.