Why do the first and second laws of thermodynamics not contradict each other?
It is something of a historical accident that entropy has units of J/K.  It came out of the fact that the connection between heat, temperature, and energy was not obvious to early scientists, and so they effectively picked different units for measuring temperature and for measuring energy.   

In the more modern statistical interpretation of entropy, the entropy of a system is simply a number.  Specifically, if the number of microstates associated with a given macrostate is $\Omega$, then $S = k \ln \Omega$.  The number of microstates ($\Omega$) is just a number, without any units, and therefore so is $\ln \Omega$.  You can see that we actually have to insert Boltzmann's constant, with its units of J/K, to make the units "come out right".

Arguably, a more natural way to define entropy would be to just make it it a dimensionless quantity:  $S = \ln \Omega$, without the factor of $k$.1  This would be equivalent to measuring temperature in units where $k$ is equal to 1 exactly, rather than defining our unit of temperature such that $k= 1.380649 \times 10^{-23}$ J/K exactly.
If we did this, we'd be effectively measuring temperature in units of energy as well;  for example, in an ideal monatomic gas with a "temperature of 1 J", the average KE of each molecule would be $\frac{3}{2}$ J.  Quantities such as Helmholtz free energy would still have units of energy, since we'd still define $F = U - TS$, with $T$ having units of energy and $S$ being dimensionless.  

Of course, in this parallel universe where entropy is defined as a dimensionless number, another gen. chem. student would be asking why temperature is not the same thing as energy, even though they're measured in the same units.  But that's another question and another answer.



1 In fact, entropy is defined exactly this way in information theory, since there's not really a notion of energy (or temperature) to speak of in such contexts.