Okay, so after Ilya Bursov's comment I have realized I had forgotten to reset the avg after each test... It actually was logarithmic all along.

I think the program which "tipped me off" just did so many skip list accesses it led me to believe the skip list was at fault for the speed.