The beautiful paper by Torquato and Stillinger,
"Jammed hard-particle packings: From Kepler to Bernal and beyond"
(Rev. Mod. Phys. 82, 2633–2672 (2010)),
will answer many of your questions.
It focuses on spheres, but also touches upon ellipsoids, superballs, polyhedra,
higher dimensions, and non-Euclidean geometries. It is an up-to-date survey
with pages of references.
You may recognize Torquato as a primary mover in the recent spectacular
advances on tetrahedral packing.
I think that your question, made precise in some way, is likely open.
But there are octahedral packings of density 0.947, considerably higher than
the best tetrahedral or sphere packings. So a regular octahedron is a candidate answer.
Incidentally, this paper says that the notion of "random close packing" is now passé,
being displaced by "maximally random jamming," a more precise concept.
Some specific information on random sphere packings can be found
in my MO question "Average degree of contact graph for balls in a box."