Actually, there is a really interesting example of a real-world algorithm whose running time decreases with increasing input size: Support Vector Machine (SVM) training using a (specific) stochastic gradient descent approach.
In SVM training, we are after a classifier (linear in this work) that attains a certain error rate. That error rate depends both on (1) the approximation error, (2) the estimation error, and (3) on the optimization error. (1) has to do with the richness of the function class---what's the best that a (say) linear function can do on this particular input distribution? (2) has to do with the difference between measuring error on the training set and measuring error on the real distribution (or a test set). (3) has to do with how well the optimization problem is solved---in general, you cannot get a zero-cost solution on the training data.
As more training data is available (ie the input size increases), the estimation error decreases. In other words, there is less of a difference between the empirical and true error. So to get the same overall error level, we can actually increase the amount of acceptable optimization error. Interestingly, the overall effect is a net gain: one can actually run the training procedure for less time with more data.
The specific algorithm is called PEGASOS and their nice paper demonstrates this effect theoretically and with experiments. See in particular eq (10) of
Shai Shalev-Shwartz and Nathan Srebro. SVM Optimization: Inverse Dependence on Training Set Size. ICML 2008.
(Note: I kept this discussion at a very high level since the details are a bit subtle to someone without a machine learning background.)