I had no idea that contouring in pdf was so bad. You're right, I think the contours are being anti-aliased by the PDF renderers outside of matplotlib. It is for this reason I think you need to be particularly careful which application you use to view the resulting PDF - the best behaviour I have seen is with GIMP, but I'm sure there are plenty of other viewers which perform well.
To fix this problem (when viewing the PDF with GIMP), I was able to "rasterize" the contours produced with matplotlib to avoid the ugly white line problem:
import matplotlib.pyplot as plt
import numpy as np
xs, ys = np.mgrid[0:30, 0:40]
data = (xs - 15) ** 2 + (ys - 20) ** 2 + (np.sin(ys) + 10) ** 2
cs = plt.contourf(xs, ys, data, 60, cmap='jet')
# Rasterize the contour collections
for c in cs.collections:
c.set_rasterized(True)
plt.savefig('test.pdf')
This produced a contour plot which did not exhibit the problems you've shown.
Another alternative, perhaps better, approach, would be to fool the anti-aliasing by putting coloured lines below the contourf.
import matplotlib.pyplot as plt
import numpy as np
xs, ys = np.mgrid[0:30, 0:40]
data = (xs - 15) ** 2 + (ys - 20) ** 2 + (np.sin(ys) + 10) ** 2
# contour the plot first to remove any AA artifacts
plt.contour(xs, ys, data, 60, cmap='jet', lw=0.1)
cs = plt.contourf(xs, ys, data, 60, cmap='jet')
plt.savefig('test.pdf')
I should note that I don't see these problems if I save the figure as a ".ps" rather than a ".pdf" - perhaps that is a third alternative.
Hope this helps you get the paper looking exactly how you want it.