Smoothing out a list
Python 2, 104

def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)


Tries different maximum increments d, starting from 1 and counting up. Fills in gaps of each pair (p,x) of successive elements by taking every d'th number in the gap. If M is longer than the quota allows, recurses to try a higher d. Otherwise, returns a list of the added and original elements, sorted.

This does all the test cases without delay on my machine.