Now imagine a huge collection of randomly positioned small massive marbles in a volume of free space, making the entropy of the collection a maximum.
If the configuration is precisely defined, we are dealing with one specific state, having probability $1$, which means that the entropy is zero. In this sense there is no difference between a random distribution of marbles and their ordered state.
The entropy becomes a meaningful concept, if we do not know in which exact state the system is - i.e., if many random states are possible. In thermodynamic equilibrium we assume that all the states with the same energy are equally probable.
On closer inspection, the marbles are gravitationally interacting, no matter how weak. If in outer space, waiting long enough, they will move towards their center of mass.
If the marbles are not able to give away energy, but only exchange energy among themselves, they will not assemble closer to their center-of-mass, but rather continue flying around, colliding. Essentially, we have here a non-ideal gas with hard core repulsive interaction at distances less or equal the radius of a marble, and weak attractive interaction at larges distances.
My question is, will a random distribution have a lower potential energy than an ordered state?
Assuming that marbles can lose kinetic energy, e.g., it is transferred into their internal energy in collisions or emitted as electromagnetic waves (via some mechanism), then the system will relax to a lower energy state. If this energy state is unique, then we will arrive to it regardless of the initial configuration - provided that we wait long enough. If there are more than one ground state, we will eventually have equal probability of finding a system in any of them. However, the time for equalizing these probabilities may be prohibitively long, in which case one may get an impression that the system is stuck in one or another ground state - we then talk about phase transitions (see Anderson's More is different. for an excellent discussion).