I think we may be missing a piece from Darwin's original hypothesis.
An outline of the first 4 chapters of Origin of Species form the kernel of the Theory of Evolution:
1: Variation under Domestication
2: Variation under Nature
3: Struggle for Existence
4: Natural Selection
Really you can't reduce evolution to less than variations; competition (struggle) ; selection. that's about as far as you can go and still call it evolution. Even genetic algorithms which don't use living organisms at all have these 3 steps.
Most people don't have an issues with Variation any more. At one time it was thought that individual variations were not important, but now most people understand that one water bug might have significant individual differences from other water bugs and its not just people who look at each other and marvel at individual traits.
The struggle for existence was difficult for people to accept at the time, but its simply that most living things don't make it. Darwin had noticed that each spring that a typical bird pair might have 3-4 eggs in their nest but if you do the numbers it tells a story of how much of a struggle life can be even if we don't see it on a walk in the woods. If all eggs reached maturity and reproduced, a single pair of birds would generate enough birds to cover England in about 40 years. That's just a squeak under 3.5^40 without death from old age.
The struggle for existence hints how competitive Selection is. In their breeding lifetime, to have a static population of birds, a breeding pair produces 2 breeding offspring out of perhaps 14 eggs lain.
It's a given that genes don't know that they have to do anything, but if they don't work well they will not be seen again. Their host dies from a developmental issue, falls and hurts itself doesn't display the right plumage, isn't fast enough to catch its food, is so slow that it gets eaten, its seed falls on soil it cannot germinate in, etc etc.
The list is endless as to the things that can go wrong in the wild and would cause an individual to be removed from the gene pool and they don't produce offspring. All of the important qualities that genes need to have is mysteriously embedded in what we call the environment - the earth, the air, the water the behavior of other living things decide whether most genes make it or not.
If you need any more evidence that intelligence has nothing to do with evolution, then look at human beings... not getting along well with other living things well now - is that smart?
An example of selection
Since it was requested, let me expand and give a very simple example of random selection that I've always liked (Disclaimer: maybe because I made it up as far as I know!).
Take a box of 100 coins. We want all 100 coins to be heads up, but we can't individually flip any of the coins over: we can only shake the box. Note that when we shake the box - nothing is thinking or acting consciously. Genes do permute randomly and, for all reasonable approximations of infinity, infinitely, but they tend to stick around when something works. This makes evolution seem unnaturally quick to respond.
Method 1: shake the box, looking every time. There are 2^100 combinations. Getting terribly lucky we'd have to shake the box 2^97 times before we accidentally caught a box of all heads up coins. That's random chance.
Method 2: if we remove the coins that are heads up every time we shake the box, we'll be shaking the box 8 times or so. That is similar to a strong selection case in evolution: the coins which are heads up are like traits which have an advantage so they stay around. Its striking how efficient this can be and how many tremendous changes can happen in a short time if there is selection and advantage.
Note that we have plenty of bad traits here (tails up); they show up all the time - with great frequency. They just don't stick around because the struggle for existence is so challenging.
You can further get an idea of weaker selection if you can imagine that instead of the heads always staying heads, you have a little stickiness on the tails of the coins. 80% or 60 or 52% of the time these coins stick and stay as heads. It still will not be long before you find that the coins are mostly heads. 10 20 or 30 shakes of the box rather than 8.
Where do new traits come from then?
So taking all this and thinking about how new traits like eyes which had not been
seen before, the same blind and random process applies. It is better not to think of humans and human traits - we're the product of over a billion years of selection and evolution! Think how primal traits at the bacterial level emerge.
Below is a picture of salt pools in the San Francisco Bay. Evaporation increases the salt concentration in the pools and as they become inhospitable, halophilic (salt loving) bacteria take over.
The pools are colored because these bacteria have an ancient mechanism which allows them to harvest light to pump the salt out of their bodies and help create energy as well. The light is harvested in one well documented case by a retinol molecule which absorbs blue light. Retinols are a variation on vitamin A and must be quite ancient.
Yet a similar molecule, retinal, is used in human eyes as the light sensor there. A similar protein holds those light sensing molecules in both human and halophile as well. While the structure of the eye and the nervous system that processes information into the brain all came later, you can see at one point the interaction with a bacterium with light became so useful that once it evolved, it has stayed in the gene pool since the days of bacteria to be the light sensor. Vitamin A is the product of a biosynthetic pathway that very easily makes a variety of molecules. The light sensing genes that used them evolved once, but variations on it sense light in our eyes today.