That surely must be a bit too oversimplified, since that would imply that the beginning of the observable universe had more entropy than the current one (given that it was way hotter than the present)
But, coming from a high entropy state does not fit with the world we see, so we're pretty sure that the past hypothesis is true.
One of the leading theories about the early universe and how it lead to the world we know today, is inflation. In that theory "stuff" is basically created out of nothing, meaning that the early universe was small, hot, and with (relatively) few particles in a specific configuration. The inflation and reheating dramatically increased the entropy. In other words - there was much less stuff, and it needed to be in a particular configuration to expand into the universe as we know it. That is low entropy.
Note: I am not a theoretical physicist, so the above is my layman understanding of the topic.
Additionally, the Big Bang is theorised to have passed through "absolute hot" https://en.wikipedia.org/wiki/Absolute_hot
What do you mean by macrostate? If the macrostate is related to the geometry of the asteroids considered as solid bodies (and the changes in their positions and orientations) I don't see why the entropy would be lower.
In the case of the asteroids, I guess I'm thinking of number bits required to accurately model the system accurately. Is that an appropriate way to think about it?
I see it as lower because fewer cells in a matrix are needed to model the solid bodies...
But I fail to see the analogy with the asteroids. If the microstate is the atomic configuration it doesn’t seem to depend (at least significantly) on the macroscopic description of the position, momentum and angular momentum of the asteroids. The number of bits (?) is not a physical quantity (and why would you need less bits to describe the microstate?).
I hope I'm not expressing myself too foolishly, but I really don't understand it. After much effort, I feel like I have a good understanding of entropy, though. Which is what makes gravity so weird to me.
But you may not be looking at the whole picture. Just because a system occupies a smaller volume doesn’t mean the entropy is lower. In classical thermodynamics a gas can be compressed while keeping the entropy constant (at least in theory).
Edit: after a look at the first paper by Verlinde I still don’t know what are the microstates in this theory (they are related to string theory and intentionally left mostly undefined). But in any case your assumption that entropy decreases seems wrong by definition because an entropic force acts in the direction of increasing entropy.