The TLF gives some clues about the expression :

LÉGUME, subst.

[…]

II. − Subst. masc. ou fém., pop. et fam. Gros(se) légume, une légume. Personne importante ou influente dans un milieu donné. Synon. huile (pop. et fam.).Mon beau-père étant quelque chose dans les « légumes » de l’arrondissement, conseiller cantonal, si je ne me trompe (Verlaine, Œuvres compl., t. 5, Confess., 1895, p. 175).Qui lui aurait dit qu’il deviendrait une légume, un homme en situation et de cabinet (Arnoux, Paris,1939, p. 152):
3. D’une humeur massacrante à l’ordinaire, il [un professeur] se montrait charmant le samedi, dans la perspective enivrante de s’en aller bâfrer et boire, le lendemain, chez quelques grosses légumes du commerce bordelais, qui lui avaient confié leurs rejetons. Jammes, Mém.,1922, p. 22.
♦ Loc. verb. vieillie. Être dans les légumes. Occuper un poste important. (Dict. xixeet xxes.).

[…]

On peut trouver un début d’explication à cet emploi familier et argotique de légume, dans le dictionnaire culturel en langue française (sld Alain Rey).

Les connotations négatives ou positives des légumes, souvent contradictoires, reflètent leur statut ambigu. Être un légume (d’après l’anglais vegetable), c’est avoir une vie réduite aux fonctions élémentaires, celle des végétaux, ce qui est réducteur appliqué à un animal et plus encore à un être humain. Dans ce cas le langage ne retient que la qualité de végétal et non l’aspect consommable. En revanche, c’est une certaine valeur marchande qui peut être retenue dans l’expression française grosse légume, ou elliptiquement légume, désignant un personnage important.

À partir de là je me demande si l’emploi du féminin (voir mon commentaire plus haut) ne se serait pas imposé pour renforcer le fait que légume dans le sens de « personne importante » désigne une personne (et non un végétal ou quasi végétal).

Dans le dictionnaire historique de la langue française (sld Alain Rey) le premier emploi de légume dans ce sens métaphorique de « personne importante » date de 1832.

We could find the beginning of an explanation in the dictionnaire culturel en langue française (Alain Rey & al) in the ambiguous status of vegetables throughout history. Vegetables were the food of the poor peasants until kings and clergy began having vegetable gardens of their own.
Still according to the dictionnaire culturel en langue française the use of vegetable designating a person (or an animal) reduced to its bare elementary functions (it was used in English before it was used in French) depicts the vegetable attribute, whereas the use of the word to designate an important person depicts the commercial value of the vegetable.

Au départ, une grosse légume est un officier. C’est de l’argot militaire qui s’est répandu ensuite dans le civil, pour désigner une personne importante. Il semble qu’il y ait plus de détails dans le Dictionnaire historique des argots français de Gaston Esnault que je n’ai pas.

En 1854, dans son Voyage en Danemarck, …, Jacques Boucher de Perthes éprouve encore le besoin de définir le terme (les italiques sont dans l’original) :

J’abaissai mon chapeau devant cette grande autorité, cette grosse légume, comme disent nos soldats quand ils voient passer un officier général ou toute épaulette à graines d’épinards.

Ces épaulettes dites « à graine d’épinard » (à cause de leur forme) identifient les officiers supérieurs. Elles pourraient bien être à l’origine du terme légume (par opposition aux sardines des sous-officiers), mais l’étymologie est disputée.

C’est peut-être de ces épaulettes que vient aussi l’expression huile pour désigner une personne importante, même si là aussi, au-delà de l’origine vraisemblablement militaire, l’étymologie est disputée.