Two thousand cubes

A perfect cube of volume $2000$ has a surface area of $952.56...$ and edge length of $12.5992...$ . So, we look for sides $a, b, c$ that are all close to that number. $(a,b,c)=(11,13,14)$ yields the smallest surface area

$2(ab+bc+ca) = 958$

Now, but the volume is

$abc = 2002$

which we can fix by taking out 2 cubes from any corner which doesn't change the total surface area.

A 12x13x13 box would contain 2028 unit cubes with a surface area of 962. This is the minimum for 2028 cubes as it is very compact. Removing cubes one at a time will not reduce this unless we remove an entire edge. Removing an edge will reduce the surface area by 2.

If we remove two edges of length 12 we are left with 2004 cubes and surface area 962-4=958. Removing four more cubes cannot reduce the surface area further, so the answer is $\boxed{958}$