Kind of amazing that something that can be expressed in ~1000 lines of code has completely turned the world on its head.
Even standard-compliant JPEG decoder would be hard to squeeze without some serious codegolfing. Discarding some barely used features gets you close to that limit, though [1].
Smallest popular TCP/IP stack [2] is ~20kLoC.
A single concept might be implementing just ARP or a discrete cosine transform. If you wanted to do a full TCP stack or JPEG decoder, that would make a lot more sense after building their internal components one by one.
If you could exhaustively list all the interesting algorithms (hard but feasible) you could potentially prove a lower bound for each one's complexity by writing a shorter than n implementation (hard, probably infeasiblel and show positively that GP's prop isn't true. On the other hand showing that it was true would require either some very clever proof which can't apply to all programs, but somehow only these interesting ones (very likely impossible) or enumerate all C^n programs where C is the number of possible lines (something like 64^80) and show that none of them implements at least one of the interesting algorithms (absurdly impossible).
The key point here is that we are looking at algorithms already discovered in human history rather than enumerating all possible interesting algorithms. Of course there is an interesting algorithm that is very large, but humans don't discover them in practice. If you look up a list of greatest algorithms in history, they will be rather small in length. Many of them can be sketched in a whiteboard
I think that what is happening here is that our minds just can't hold billions of concepts at once. So if you have an algorithm with billions of things, it was most likely produced by a machine. Handcrafted things, on the other hand, are smaller in comparison
Another thing is that our minds like conceptual simplicity and view simplicity as a kind of beauty. So if we have a great algorithm but it is too large, we look for ways to express them in succinct ways (the right abstractions can help with that, and also help with understanding the algorithm better). We end up succeeding because the algorithms themselves had low Kolmogorov complexity (and thus, if they are too large they probably can be further compressed)
Who knows, there might be a warp drive in there somewhere!