How can we think about entropy in these situations? To my knowledge all of these structures are born out of gravitational interaction. However, it would seem that the formation of these more organized structures conceptually violates the second law of thermodynamics. Is this dilemma arisen from my flawed understanding of thermodynamics or are these structures actually in a way defying an increase in entropy?
John Baez has a nice article on his website that goes into some detail on this question.
Broadly, your intuition is right that at face value, it looks like structured systems are born out of nearly featureless initial conditions. However, as (for instance) a gas cloud collapses into a galaxy, it heats up (see the virial theorem, a theorem any self-respecting physicist should derive at least once). As it heats up, it radiates, and comparing the entropy of the initial cloud and that of the collapsed cloud and the emitted radiation, you'll find that entropy has increased overall, and the second law is safe.
A living organism is a very complex biological machine that seems to defy the laws of thermodynamics. The number of states a piece of matter forming a machine can be in in vastly less than if that piece of matter were in thermal and chemical equilibrium at ambient conditions. This means that machines cannot function for long if they can only interact with an environment that is at thermal equilibrium. Random perturbations caused by the environment will on the long run compromise the machine and will need to be reversed by the machine. However, the laws of physics do not allow the machine to implement an algorithm that can erase random information from the environment.
Time evolution is a unitary mapping which will always map two different initial states to two different final states. The final state then always contains the information about the initial state. To erase information you would need to be able to map two different initial states to the same final state, then the final state would no longer contain the information about which initial state gave rise to it. But this is a forbidden process. So, how can living organisms exist at all?
One can deal with this problem if the machine is able to make contact with another environment from which it can extract energy at a lower entropy than from its local environment that is causing the perturbations that it needs to reverse. In case of life on Earth, that environment is the surface of the Sun, photons from the Sun have a very low entropy per unit energy compared to energy from the local environment here on Earth. These photons (or other energy forms derived from them) can be used to reverse the perturbations by dumping any waste energy from the low entropy source into the local environment.
Even though the number of final machine states is then less than the number of initial perturbed machine states, the total number of states including the states the photons can then increase. A one to one mapping between initial and final states is then no longer incompatible with the machine than can reverse perturbations and return from a larger set of perturbed states to a smaller set of states.