It helps to come up with some metrics that indicate how good a solution is to you. What is the disadvantage of having wide intervals? Can you try to calculate a number representing how much such hurts your results and numbers for how much the quality of the points affects the value of a particular solution? Even if you don't get great metrics, just attempting to may help you understand more precisely how you want to balance these goals against each other.

I might approach this problem from "the opposite" direction. Add the points one-at-a-time, in order from highest to lowest quality. As you go, keep track of the largest interval left. When the largest interval is close enough to $length/($finalPointCount+1) (perhaps as a function of the quality of the worst point required), then switch to removing points.

Starting at the worst point, remove it only if doing so wouldn't create an interval larger than desired (so you'd never remove the last point added). Move on to the next-worst point...

I don't think you can absolutely predict how many points you'll have at the end of such a run. But you can specify the minimum interval size you'd get and the minimum point quality.

A few other methods come to mind but they are all motivated by possible metrics I've guessed at (such as, is it relatively okay to have a large interval if it is "next to" a really high quality point?) and I don't know which metrics make sense for your problem, so I'll wait for more info at this point.