Alex, the covering radius of a lattice is the circumradius of the Voronoi cell around the origin. For a lattice, all Voronoi cells are translates of each other. The points on the boundary of the Voronoi cell that achieve that maximum distance from the origin are called the deep holes. Let's see, the Voronoi cell around the origin is the set of points that are closer to the origin, or no farther away from the origin, than to any other lattice point. So, in $R^2,$ for the standard hexagonal circle packing the cell is a regular hexagon, which you can easily draw by hand. The covering radius is then the distance from the origin to a vertex of the hexagon. For a slightly skewed lattice and slightly irregular (but centrally symmetric) hexagon, the covering radius would be the distance to the farthest vertex from the origin. This is mostly from chapter 2 of SLG, which is Sphere Packings, Lattices and Groups by J. H. Conway and N. J. A. Sloane. Let's see, for the standard integer lattice in $R^2$ the cell would be a square.
It is known that calculating the Voronoi cell, deep holes, and in particular covering radius is NP-hard, the number of steps required grows exponentially with the dimension $n.$ The great advance in the LLL algorithm is that it finds fairly short vectors, where the steps grow only as a polynomial in $n.$ And of course, for very small $n,$ it finds the shortest vector. Meanwhile, the algorithm finds an entire basis, so the comments about possible minimality refer to the first reported vector in the (integral) basis. A full basis is a different problem from a single short vector, in dimension 100 you would usually rather have a basis of all medium length vectors than a single very short one and 99 long ones.
Perhaps this will help, there is a useful language called Magma that has this,
Meanwhile, for examples of lattices, with an emphasis of root lattices for Lie algebras, see here. Note that Gabriele Nebe has written an article finding all lattices with covering radius below a certain bound, in her normalization that is $\sqrt 2.$ This anticipates me and Pete Clark of MO,
so it is not clear what will be published on that...