My semi-educated guess is that one extended sense of sub-, "under", is "raised up by something below", especially to ground level—that is, supported or providing support. The English word "support" might itself illustrate this (see below).
Another example is suggestum, a raised platform such as a stage or pulpit, or a mound, from suggero < sub- gero, "I carry/bear/hold from below."
So, in Latin, sub's core meaning of "under" is often extended or specialized to mean "exerting a force from underneath the object in question", especially a force that helps stabilize it or provide it a ground to stand on.
The idea of "not enough" is itself just another extension of "under", equally as reasonable as "providing a stabilizing force from below." Other extended senses are "pushing down from above" as in supprimo, "I press down, hold in check", and "sending downward" as in subverto, "I overturn, topple, ruin". The various extended senses often contradict each other, but there's nothing unusual about that. The primary sense of per is "through", which is extended sometimes to "thoroughly, fully, greatly" as in perplaceo, "I please greatly", and sometimes to "badly, wrongly" as in perversus, "overthrown, ruined, wrong, evil," and perhaps "twisted" (in its English sense as a synonym of "perverse").
Etymonline suggests that sub-/sup- might come from older roots ex-upo-, meaning "out from under" or perhaps "coming from below"—so sub- in this sense of exerting a force from below might even be felt as more fundamental in Latin than merely "under".
Some more examples:
Surgo: "I arise", "I elevate", from sub rego. In an insurrectio, "rebellion", subordinate factions in a society "rise up" to overthrow those who are "on top".
Supporto: "I bring to a place", especially supplies. Perhaps the metaphor is that of carrying supplies "up" from where they are to where they are needed. I don't know when "support" got its modern meaning of "lifting up, providing a foundation", but it would appear that sub's sense of "exerting force from below" itself exerted a lot of force for a long time (though no longer in modern in English).
Suborno, "I equip", "I instigate", and suggesto, "I supply", "I advise", "I bring to mind", the verb at the root of suggestum, "a raised platform", suggests that sub- pairs well with verbs meaning "fill a need". Suppleo would seem to echo this notion (and/or vice versa). It's easy to think of "filling" a need similarly to "filling" a bucket—filling tending to start from below until the bucket is full, though I know of no specific evidence of this metaphor.
Another sense of sufficio is "I substitute for, I fill in for". Many of the examples in Lewis & Short seem to involve someone from lower in a hierarchy "coming up" to fill a recently vacated higher position. For example, a suffectus consul is a supplementary consul: a vice consul who finishes a consul's term (or perhaps someone appointed to be available to fill in as needed).
The many senses of subicio seem to illustrate the many Latin ways of extending the core meaning of sub-, generating contradictory senses of the very same word: "I launch downward", "I supply", "I lie beneath", "I place under" (as under a category), "I subject to", "I forge" (substitute worse for better), etc.