The key change to make is to follow the line all the way from centroid to the first border beyond the point we're trying to compute the nearest border of. That way if we're dealing with concave shapes (like above) we can pick better select the nearest border, which may be between the centroid and the border. It still won't always be correct for portions of some complex concave shapes, but it shall come close enough in most cases.
And now, back to bed. Now that its not bugging me I can hopefully sleep.