I had this exact scenario come up at my table recently, I ruled against it. Downvotes be damned, here’s why.
Is it a feature: Yes
Is it a proficiency: Yes
Is it a starting proficiency: Debatable
The marked answer ignores the relationship proficiencies are to class features (proficiencies are features) and the exclusion specificity in the multi-class rule. You don't just get ALL features.
For the marked answer to have credibility you need to also ignore the key-word Proficiency all together and focus instead on the subcategory of the feature (1st level Order Domain Feature). They could have used any other words to name this feature instead of Bonus Proficiencies (A Hard-Knock Life for example), they do for all other features. AFAIK, errata for Tasha’s doesn’t rename this feature.
My core argument is how the feature is being granted to the character. It’s given to them in the form of a Bonus Proficiency. This feels to me like an order of operations issue, with specific wording.
At that point is where I think the specificity of the multi-class rule applies, it’s a Proficiency (first) granting a 1st level Order Domain feature (second).
This is complicated by the way the player’s handbook reads (PHB page 57):
As a cleric, you gain the following class features.
So, Proficiencies themselves are a type of Class Feature.
Our order of operations is:
Class Features: Divine Domain(feature): Order Domain(subclass): Bonus Proficiency (proficiency): 1st-level Order Domain Feature (feature)
The multi-class rule is being specific about “Starting Proficiencies” (remember, a proficiency is already a type of class feature).
Is it a “Starting Proficiency”? I think this is a fare counterpoint to my argument, since were traveling down the path of specificity they use the word Starting to differentiate in the multi-class rules. Maybe it is, maybe it isn’t. I can’t find a solid definition for the term Starting Proficiency in the books or errata (No, I don’t own everything in Beyond. No, I don’t own every book).
Left to my own devices, my definition for Starting Proficiency then becomes, any Proficiency granted to a class at 1st level as a Class Feature. This Bonus Proficiency fits the definition, again, because they used the word Proficiency to name the class feature.
I have a habit of doing this ceremony at my table called “House Cleaning”. I make a controversial call at the table during play, I make a note, I try to fix it in next session after doing some research. It’s important to me to try to play fair.
This was way more research than I’ve ever done on a single controversial call, the community accepted answer just feels wrong to me with not a good counter-point argument represented.
Not gaining this proficiency doesn’t restrict the Order Domain at all, additionally it doesn’t seem to hinder any of Tasha’s optional class features that use the keywords Bonus Proficiency.
The balance of the game is already player favored; this seems trivial to lose over the advantages of the multi-class in general.