I think people are misled because it's difficult to really grasp the very high dimensionality of the space ("morphospace") in which organisms sit. There are many, many directions for incremental change to go in, and evolution just needs there to be an improving step at each point along the path. In a low dimensional space it would be easy to get stuck in local minima, but as the number of dimensions increases that's harder and harder.

Evolution can be very easy given time. Trees independently evolved from non-tree plants something like 100 times, for example.