This feeling is accounted formally, at least in part, in a form of logic that has been constructed to represent 'Intuitionistic' mathematics.
Brower, the intial framer of intuitionism, became famous for the 'hairy ball' theorem in topology -- basically, that you cannot uniformly paint a sphere entirely with non-overlapping brush strokes along the surface of the sphere, there will always be an overlap or there will be points left that have to be filled in by the point of the brush at the end -- you can't comb a hairy ball. But he did so by 'reductio ad absurdum', by assuming there is no flaw at any point and getting a contradiction, in a way that does not identify the flawed point.
He felt he had done the world something of a disservice by answering the question. What was really needed was a 'constructive' answer that identified the point, or continued search for a solution. So he stepped back and tried to capture what would happen to mathematics if we took this dissatisfaction seriously.
So you are not alone in your feeling about the two assertions, there has been a school of math that feels that way too. We intuitively expect more out of an existential quantifier than the assertion of possibility. We are fairly comfortable with universal statements about entities which have no reason to believe exist being nominally true and letting them go. All unicorns are black, and all of them are also white. Until we meet an actual unicorn, we are fine with that to a large degree.
But for an existential statement, this is not satisfactory, we would really like a stronger sense of proof. Although assertions about situations in which there is no evidence in general are really neither true or false, unproven existential statements are less true, in an important way, than unproven generalizations.
This means that existential statements should require stronger evidence than the negations of universal statements, so De Morgan's laws, as they apply to quantifiers, are overly strong, and we need a different way of looking at negation, especially when it is applied over infinite or other merely potential sets.
Since Brower was a better mathematician than philosopher, his own internal study of intuition became less than compelling. (It also happened in Germany right before Nazism, so it got interpreted as a sort of Nationalism and anti-Semitism, since the deepest thinking about infinities, logical complexities, etc. near that time originated from Jewish, Polish and English investigators.)
But there are clearer formulations of this kind of thing that keep arising, and it seems this will not stop until some school of Intuitionistic or Construtivist Mathematics captures what Boolean logic takes out of more natural logic in a way that is adequately clear.