From a general game design theory standpoint i think its good to have a skill system where you need to take some skills you might not really want in order to progress down the tree. The reason is this gets around the problem that occurs with min/maxing of removing more specialist or secondary abilities.
I always like to compare skill systems in games to hard class systems. Hard class systems, where you simply have a set of pre-defined abilities which unlock as you progress through the game, have some advantages. Namely they can contain thematic class skills or abilities that no player trying to build an optimized character would ever take. This allows situational abilities or fluff skills to be included which unlock certain interactions and situations in games that nobody would ever encounter otherwise. In a class based system people do not complain about these abilities, because they are just class characteristics. In skill based systems where a good skill is separated from you by first having to select a lesser skill, it feels like a 'skill tax' simply because the player is now made to actively select and confirm a skill they dont want.
This is a psychological problem and could have a simple psychological solution. Find and designate the skills which are more of a gateway, something you must pass through which are more of a bonus perk for the two skill point costing skill following it, and make their icon smaller on the skill tree. The game acknowledging the skills as being less useful may be all that is required to alleviate the sense of wrongness a player might feel.
Of course acknowledging some skill pairings are less useful does indicate a balance pass to ensure the following skills are worth the extra point investment.
Further, the frustration may simply stem from people not feeling their builds are completed. This might be a thing that would go on forever untill you have as many skill points available as skills, or it might result from actual deficiencies in skill tree layout. Certain skills fit certain thematic builds better than others, running into situations where you are always a few skill points short could well be an objective and real consequence of synergistic skills which the player wants to connect up simply feeling like a punishment requiring the loss of other synergies. Ideally in a skill building system its most satisfying for a player, after planning out their build, to definitely be able to conclude "yes, i could not improve this, these are the optimal skills for what i envision the character to be".
I also think the skills with fleet size conditions should maybe have secondary effects that do not get diminished as well, simply to avoid the feeling that a skill becomes worthless. While in practice these skills always have some effect, they dont feel like it when you are sitting there trying to make a build, humans are simply not so good at assessing variables like this. Giving the skills something solid for the mind to latch on to could also alleviate the discomfort involved in taking them.
