The structure we see in the Universe has formed from the gravitational collapse of the matter that was once an almost smooth density field of gas ("baryons") and dark matter$^1$. The word "almost" is important here, for if it had been completely — or even non-completely but much more — smooth, then the collapse would not have had the time to happen before the expansion of space has diluted the matter enough to prevent any collapse, and we would never had come into existence.
That is, the density field was slightly clumpy, and these clumps — or overdensities — existed on all scales.
But calculating which clump sizes collapse first — stellar-sized, galaxy-sized, cluster-sized, etc. — is far from trivial. Analytical attempts has to make several approximations, but can still make quite meaningful predictions which have subsequently been backed up and refined by numerical simulations, and by now, although many loose ends still exist, we have a rather good picture of structure formation:
Gravitational collapse
An overdensity is denoted by
$\delta\equiv\rho/\langle\rho\rangle - 1$, where $\rho$ is the density of the overdensity and $\langle\rho\rangle$ is the average density.
The evolution of overdensities under the force of gravity can be calculated exactly for $\delta \ll 1$ using linear perturbation theory, but when $\delta$ becomes of order unity, the non-linear regime is entered, and severe approximations must be made, so one turns instead to numerical simulations. It turns out that if $\delta\gtrsim1.68$ (i.e. if a region in space has a density which is 2.68 times the ambient density), it will collapse. The answer to your question is then given by what size of clumps first reach $\delta\gtrsim1.68$.
First clumps
Primordial quantum fluctuations$^2$ grew in size during the (admittedly still pretty blurry) inflation, a fraction of a second after Big Bang. In the young Universe dark energy was negligible, and the dynamics of the Universe was dominated by matter. Because dark matter comprises $\sim5/6$ of the total amount, we can initially neglect the presence of gas, but when the density becomes very high, gas pressure builds up and counteracts the collapse.
The overdensities amplified as matter started to collapse. It turns out that the density fluctuations are larger for smaller scales, so the smaller the clump, the sooner it will collapse. This results in the so-called "bottom-up" formation of structure, which is in contrast to what was originally thought; namely that galaxies formed "top-down" in a monolithic collapse (Eggen, Lynden-Bell, & Sandage 1962).
However, this approach neglects both gas and the motion of dark matter particles (treating it as so-called cold dark matter). Taking into account the effects of this puts a lower threshold for the masses of the structures of $\sim10^5$-$10^6M_\odot$ (e.g. Naoz et al. 2006; Yoshida 2009). Hence the first structures that formed are believed to be minihalos roughly the mass of globular clusters.
Stars, galaxies, and clusters
Stars consist of collapsed gas and almost no dark matter, and the formation of a star thus needs the theory of hydrodynamics rather than just gravity. In order for matter to collapse to such dense structures as stars, it must get rid of much of its energy. This is not possible for the collisionless dark matter (at least in the normal sense, but this post), but gas, which can collide and cool by radiating, is able to do so$^3$.
Through radiative cooling, the minihalos thus fragmented further into first gas clouds and then the first stars when the Universe was a few 100 million years old. Subsequently conglomerations of stars merged into galaxies, which eventually formed sheets, filaments and clusters of galaxies.
Dust
The first stars were formed out of pure hydrogen and helium (and small amounts of lithium), and the material for making planets did not exist. But when these stars — which were very massive — exploded as supernovae and polluted the interstellar medium with metals$^4$ and stardust$^5$, the formation of less massive stars became possible$^6$.
Planets
Dust particles stick together to form pebbles, rocks, and planets. Planet formation is probably not possible for too massive stars$^7$, but with the formation of small stars this became possible.
Timeline
We can make the following timeline:
- Minihalos
- Gas clouds
- Stars
- Galaxies
- Stardust
- Planets
However, note that the merging of minihalos to larger "galaxies" (without a significant amount of stars) also may happen at earlier epochs, and in particular that star formation (and dust and planets) is a continuous process which still takes place today (although the bulk of the star formation took place when the Universe approximately 3–6 billion years old (Madau et al. 1998)).
$^1$And radiation, which actually dominated the energy density until the Universe was $\sim50\,000$ years old.
$^2$The term primordial quantum fluctuations might be the coolest term in physics.
$^3$There are hypotheses of so-called dark stars, but that's beyond the scope of this text (primarily because I don't understand them).
$^4$For an astronomer, the term metal means any element heavier than helium. It's easier this way.
$^5$Astronomers just call it "dust", and use only the term stardust when talking to non-astronomers, in order for them not to fall asleep.
$^6$The reason is that with the many possible electronic transitions of metals, the gas has more ways to cool, and hence may collapse at earlier times, before the proto-star clump reaches high masses.
$^7$Because the high radiation pressure of very massive stars blows away and/or destroys the dust (I think, but this is not my expertise).