Because this is a difficulty 2, I only considered rectangular cuboids.  Charlie seems to have followed suit.

But, more generally, some mathematicians define a cuboid as convex polyhedron bounded by six quadrilateral faces, whose polyhedral graph is the same as that of a cube.  If we use this definition, then there is no absolute answer.

Consider a rectangular cuboid with width w, height h, and depth d, where w, h and d are integers and w*h*d > 1000.

We can reduce the surface area and the volume by making the 4 vertical edges non-vertical but still parallel to each other, transforming two of the faces into parallelograms.  As we lean these edges over, the distance between the base and the top becomes h'.  The volume of the non-rectangular cuboid is w*h'*d.  We can get this volume arbitraily close to 1000 by making h' arbitrarily close to 1000/w*d.  The surface are is 2*(h'*w) + 2*(wd) + 2*(hd).  Since h' can be arbitrarily close to 1000/wd, this expression can be abitrarily close to 2000/d + 2d(w+h).  It is not too difficult to work out that this expression is minimized (and equal to 618) when d = 8 and w and h are both greater than 8 and sum to 13.  Values of (w,h) which work are (9,14),(10,13),(11,12),(12,11), (13,10) and (14,9).  Note that 618 is less than the rectangular cuboid minimum surface area of 620, and that the first and last of these pairs correspond to the rectangular cuboid with that surface area.

And that is about as far as I can take this.  Lower surface areas are presumably available if the height is leaned over away from both vertical axes, leaving four parallelograms and two rectangles, but I think it it requires calculus to work out what the minimum is.

Even better (or worse), one could lean over two different dimensions, and presumably get a lower minimum.  Again, calculus.

And finally, I think that all faces can be parallelograms, leading presumably to an even lower minimum surface area.

But the puzzle author did not intend any of this, so I will stop here.