First, there is indeed nothing mathematically very deep in this observation, and I agree that the word "breakthrough" might be exaggerated. But on the other hand lots of very deep ideas look trivial once spelled out explicitly. Moreover being younger than Voevosky I have never been really exposed to the idea that categories were sets of higher dimension (but this indeed appears in the early work on higher categories, typically in Baez & Dolan's work), so I can't comment on how important it was to understand that this is not a good point of view. But I can give some context on what Voevodsky probably meant here.
One thing to understand is that, like many mathematicians and most category theorists, Voevodsky is very attached to the "principle of equivalence" saying that when talking about categories you should only use concepts that are invariant under equivalence of categories. For example, in his work on contextual categories, he renamed them "C-systems" because he didn't want to call them categories as their definition is not invariant under equivalence of categories.
Now, if you follow this principle of equivalence very strictly, talking about "the set of objects of a category" is not meaningful (i.e. break the principle of equivalence):
equivalent categories can have non-isomorphic sets of objects.
So saying that a category is "a set of objects together with a set of arrows having a certain structure" is incorrect from this perspective.
It is true that if you have a set of objects and a set of arrows with the appropriate structure you get a category, and it is also true that any category can be obtained this way, but you cannot recover the set of objects and the set of arrows from the category without breaking the principle of equivalence. To some extent the set of objects and of arrows with the appropriate structure is a "presentation" of your category.
What is meaningful though (i.e. respects the principle of equivalence) is that a category has a "groupoid of objects" $X$, with a bifunctor $Hom : X \times X \rightarrow Set$
From the point of view of the principle of equivalence, a category is really a groupoid with structure. Moreover this structure is a very natural categorification of the notion of poset:
A poset is a set X with a function $X \times X \rightarrow Prop$ satisfying reflexivity, anti-symmetry and transitivity.
A category is a groupoid $X$ with a functor $X \times X \rightarrow Sets$, satisfying some conditions. Reflexivity corresponds to the existence of an identity, transitivity corresponds to the composition operation, and anti-symmetry corresponds to the fact that in the end one wants $X$ to be the core groupoid of the category.
But if you really take the principle of equivalence seriously, you cannot define what a "groupoid" is, you have to take it as a primitive notion that you axiomatize. But this is not really different from the fact that you cannot define what a "Set" is, you can only axiomatize what you can do with sets.
It is in this sense that groupoids are "higher dimensional sets" and categories are groupoids with a structure.
This has been made even more clear with the theory of $(\infty,1)$-categories, where it is completely clear that $\infty$-groupoids play the role that sets played for ordinary categories. (The $(\infty,1)$-categorical Yoneda lemma is in terms of functors to the category of $\infty$-groupoids etc...)
Another way to say this is that in the $n$-categorical hierarchy "0-groupoid"s are just sets while $0$-categories are posets (if you consider them as $(n,1)$-categories for varying $n$...)