I really liked the approach my stat mech teacher used. In nearly all situations, entropy just ends up being the log of the number of ways a system can be arranged ( https://en.wikipedia.org/wiki/Boltzmann%27s_entropy_formula ) although I found it easiest to think in terms of pairs of dice rolls.
And this is what I prefer too, although with the clarification that its the number of ways that a system can be arranged without changing its macroscopic properties . Its, unfortunately, not very compatible with Shannon's usage in any but the shallowest sense, which is why it stays firmly in the land of physics.
In the continuous version, you would get log(V) where V is the volume in phase space occupied by the microstates for a given macrostate.
Liouville's theorem that the volume is conserved in phase space implies that any macroscopic process can only move all the microstates from a macrostate A into a macrostate B only if the volume of B is bigger than the volume of A. This implies that the entropy of B should be bigger than the entropy of A which is the Second Law.