There are two parts to this. One is the representation: Neural Net vs Program. The other is the search approach: Back propagation vs crossover and mutation.

Your smoothness argument applies to the search approach. I would say "smooth" is not enough to describe the search space of real world solutions. I would rather call it fractal like. There are many smooth areas in a visualization of the Mandelbrot set. But the most interesting things happen in areas that are not smooth but follow some delicate logic. You find tiny local minima there that are hard to reach via gradient descent.

Genetic algorithms have a lot going for them in this type of search space. To pick one factor: GA's distribute the search power so that areas of the search space that are more promising get more resources. Similar to the optimal approach to deal with so called "multi-armed bandit" problems, GA's divide the search space in an optimal way, computation wise.