Entropy can be understood as the degree to which a system's microstate (the details of exactly what all its component parts are doing) is not fixed by the constraints imposed by the system's surroundings. In the case of a gas (which is a good way to think of the early universe, ignoring the fact that it is really a plasma) the microstate is fixed by specifying the combination of position and momentum for each particle. We can then measure the entropy by the area of the region of a momentum/position plot that is filled by the possible states of the motion of all the particles. The following diagram shows four example cases. In each plot, the ellipse is intended to show, approximately, the range of position and momentum values of the gas particles.
I have labelled each example with a comment on temperature $T$ and density $\rho$. A low spread of momentum ($p$) values indicates a low temperature. A low spread of position ($x$) values indicates a high density. The area of the ellipse indicates the entropy. The four cases are self-explanatory (I hope).
It is true that, other things being equal, a high temperature will lead to a high entropy, because the range of $p$ values increases. However, it does not always happen because a high density brings the range of $x$ values down, and this lowers the entropy again.
The early universe is an example of case D.
The subsequent evolution of the universe is largely a movement from case D to case C. This is called an adiabatic expansion, in which the entropy does not change, even though the temperature falls.
To summarise, there is no general relation which says that hot things should have either high or low entropy, if they can also be dense. High density tends to bring the entropy down.
Finally, a comment on the early universe. There is no need to bring in the word 'infinity'. All we know is that the very early universe was very hot and very dense. At sufficiently early times it was in a parameter regime where all our knowledge of physics runs out, but this does not mean we know it was infinite in any respect (whether in terms of kinetic energy or density or volume or other such parameters).