Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first?
Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the quality of the solution obtained. Indeed, remember that we are dealing with an NP-hard problem.

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can prove that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $O(\log n)$, where $n$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.