Your first issue is, how do you define "fairly" adding a skill? We'll keep asking that along the way.
"Mechanically" adding a skill
This seems more in line with what you're trying to figure out.
The simple answer, you just add it to the list. But simple doesn't tell the whole story.
What ability score are you tying it too?
Here is a breakdown of the current skills:
||Acrobatics, Sleight of Hand, Stealth
||Arcana, History, Investigation, Nature, Religion
||Animal Handling, Insight, Medicine, Perception, Survival
||Deception, Intimidation, Performance, Persuasion
- There are NO Constitution-based skills. Your example gives two skills that do, so you need to tread lightly with creating those as there may be a developer reason for avoiding it. The reason could be as simple as, no one has Constitution as a dump stat so everyone should at least be +0 at the skill. Whereas everything else has potential for being "bad". Just a guess.
- Dexterity, Intelligence, Wisdom, and Charisma all have 3-4-5 skills attached to them. That means adding more skills to these abilities will increase the power of characters based on those abilities. In other words, characters weak in these abilities will become more weak as they are not as useful for even more skill checks.
So depending on your definition of "fair", adding skills based on Strength would make steps to even the playing field, but some skills wouldn't make sense as Strength-based. Adding them to Dexterity would be the next lowest score. Adding them to Wisdom would make 6 skills (out of the current 18 total) would mean that one-third of all skills are tied to Wisdom meaning low-Wisdom characters are even more "back of the bus".
How do you gain the skill?
All characters learn skills in at least two ways--by class and by background. Some will also get one or two by race. By race and by class have predefined lists of what skills you do, or can, learn. For instance, Tabaxi automatically specifically learn Perception whereas classes learn 2, 3, or in one case 4 skills, from a short list. Sometimes the character can pick up one more via a sub-class. I'm not sure there is a "fair" way to add new skills to classes; it would be a trial-and-error thing. Same with adding by race; they already are tuned to be balanced. It would also mean that your players would have to choose what they play based on how you allocate the new skills instead of what they want.
Which leaves backgrounds... Backgrounds come with two predefined skills assigned to them, but per the rules, you are allowed to work with your DM to mix and match your own background and thus can select one of the new skills. But since backgrounds max out at two skills, dropping an existing skill for a new skill better be important. The skills you have listed are very specialized and players have no idea how relevant they will be to the campaign.
From a practical stand point, linguistics is based on Intelligence so most likely to be picked by Int-based classes (for maximum effectiveness). So that means Artificer and Wizards. But both only have 2 skill slots based on class, and for Wizards, one of which is almost always Arcana, which means they only have one class skill slot left. If available for the class, should they choose it on a skill that may or may not prove useful? Should they drop something from a background in order to squeeze in linguistics?
Or should the Bard, Sorcerer, Warlock, or Wizard just learn the comprehend languages spell?
With an average of only 4 skill slots available, picking an untested/unknown skill will not be a high priority.
To counter this, you can give everyone an extra skill slot. This would be a bit overkill if there is only one new skill but since you're introducing four, it is an option. However, unless you say, "It must be one of the new skills," there is nothing compelling to players to not choose something they know will be useful. And if you do force players to choose one of the new skills, four will pick the one that most closely relates to their modus operandi, while the rest pick at random to give advantage to the others.
Player 1: My Rogue with the high Charisma will take linguistics. That way as I learn their language I can sweet talk them into stuff.
Player 2: My Druid with Goodberry will learn cooking. Maybe I can make a Goodberry pie for even more healing.
Player 3: My Sailor is already proficient with Navigator's tools, so this navigation skill will mean I always get Advantage, right?
Player 4: My half-orc Barbarian will take endurance, because.. yeah.
They could also pick it up via a number of feats, but I'm not going to detail all those out. It's just more options.
In this case, "fairness" will be based on how the characters pick up the skills. As the DM, you better explain at session zero (or in your case session 16) that the characters will need these skills and what allowances you're making so they are not losing out on skills that fit their planned backstory or are vital to the class.
How often is the skill useful?
Are these skill only useful during the first part of the campaign, or will they keep coming up throughout the whole adventure?
Your example was that the party is on a continent where the locals don't speak Common. So, yes, when they first arrive, there is going to be a language barrier. But as time progresses, wouldn't they learn the language enough so that skill checks become pointless? By 5th level, a number of casters can get tongues and solve the whole problem. Couldn't they draw (or buy) maps so navigation is no longer an issue?
There are very few "must have" skills; Arcana, Stealth, Investigation, Perception to name a few. But there are a lot of skills that might never come up (History, Religion, Animal Handling, etc) based on the setting, so there is always a risk of useless choices.
But if you structure the campaign that these new skills are vital in tier 1 and 2 and redundant by tier 3, I would say they are not "fair" to the players as you are railroading them into wasting a resource. With the exception of Bard (talked about next) every character has a finite amount of skills they can learn. By making these extra choices a low-level requirement and a high-level space filler, with no way to swap them out (like spells), then the skills are not "fair", they are a tax.
Expertise and Jack of all Trades and Reliable Talent, oh my
A lot of this already works itself out. You can't say it's unfair to get expertise in Cooking, but not unfair to get expertise in Stealth. The same can be said for Reliable Talent. If you took the time to be proficient in a skill, having an automatic take-10 is not a big deal. A lot of these things have the trade off of investing levels into a class. Sure you are better at skills, but you don't get extra attacks for instance.
Jack of all Trades, is only slightly different in that the bard gets more things, instead improving something they are already skilled at. So the more skills you add, the better the feature becomes. It maxes out at +3 to a skill check at the top levels, so nothing that will kill bounded accuracy.
So is it "fair" with these features? You're giving a slight edge to Bards, but otherwise unremarkable.
Will the skill check be based on an individual or in group checks? Contested against something else?
If they are generally based on individual then players will just spread the love. One character takes it too excel and other takes it to help the first character and grant advantage.
If they are generally based on group checks (I could see endurance as the only practical example of this) then you may see an upswing in this skill.
Also remember that some skill checks are not against a DC but are contests. For instance challenging one creatures deception against another's insight. Will there be opposing skills for the one you're adding?
This consideration is less about "fair" and more about something to think about.
Does the skill bring something useful to the game?
I use this example a lot. I forget where I read it, but early on in my DnD playing there was an article about changing rules. The argument went something like this:
DM: I've got this cool new concept. Instead of air, the world is nothing but carbon dioxide.
Player: But then how will we breathe?
DM: You'll all have special respirators.
Player: What about NPCs? And monsters? How will they breathe?
DM: All the people will have one. And the monsters have adapted.
Player: But what if mine breaks? Seems pretty easy considering all the fighting we do.
DM: They can't be broken. They just always work.
Player: If everyone has a respirator, that never fails, and we can always breathe normally, tell me again why we are getting rid of air?
So does adding these skills add something to the game, or can you use existing rules?
As pointed out above, why get Linguistics when there are spells (comprehend languages, tongues, etc) and features (Monk's Tongue of the Sun and Moon) that will presumably serve just as well. The Navigation skill would also better be served with the Keen Mind feat which gives a +1 to Intelligence and always knowing which way is north, or just proficiency with Navigation tools.
Once again, this isn't to determine "fair", but to think about usefulness.
Does the skill bring something bad to the game?
Xanathar's introduced tool proficiency and the symbiosis with skills.
By adding new things there may be deeper repercussions; like my example of having a navigator skill and navigator tool proficiency. Is it redundant? Give advantage? Somehow separate?
Would the endurance skill help with exhaustion? With death saving throws? The half-orc's Relentless Endurance?
This is less about being "fair" and understanding how one change can have rippling effects.
Can these be handled better with existing skills/features/proficiencies?
Skills are tied to an ability; but they don't have to be tied to the default ability. The basic rules explain using a different ability for skills. So can you use Constitution (Athletics) instead of creating a new endurance skill? Intelligence (Insight) to learn a language?
And per Xanathar's:
Given enough free time and the services of an instructor, a character can learn a language or pick up proficiency with a tool.
So instead of creating a Navigation skill, give the players time to pick up Navigation Tools as a proficiency.
Once again, this isn't about "fair", this is about not over-complicating the system.
So to wrap up...
How to "fairly" add new skills
- Make sure it is adding something to the game other than complexity
- Make sure it can't be better handled by using existing or variant rules (skills with different abilities)
- Balance how the characters will learn the skill with the limited number of slots available for choosing skills
- Make sure it remains useful throughout the campaign and not just a section
- Think about all the ways the skill will be used; both in terms of situations and rolling checks
- Think about the repercussions of how the new skill overlaps spells, features, proficiencies, etc
- Limit the number of skills added; one doesn't make a big difference, but 3, 4, 5, or more and Bards get a bigger and bigger boost
- Get good with Excel/Google Sheets/Apple Numbers/other spreadsheets to create a custom character sheet
- Alternately, D&D Beyond allows you to just add skills and I'm sure other VTT would also