I understand that the entropy is the number of bits that can encode a set of messages. However, I don't understand what the min-entropy is and how it is related to entropy.
Let's describe a simple password case: if a password is 100 random bits, is the min-entropy also 100?
There is min-entropy, Shannon entropy, and max entropy. (Plus a few more definitions, but let's only focus on these.) All of these measures are greatest, for a given number of outcomes, when each outcome occurs with equal probability. (In such case all three are equal.)
$$\text{min-entropy} \leq \text{Shannon entropy} \leq \text{max-entropy}$$
Min-entropy describes the unpredictability of an outcome determined solely by the probability of the most likely result. This is a conservative measure. It's good for describing passwords and other non-uniform distributions of secrets.
$$\text{min-entropy} = -\log_2{(p_{\text{max}})}$$
Say you have an algorithm which produces 8 digit numeric password. If the number 00000000 occurs 50% of the time and the remaining $10^8 - 1$ passwords occur with equal probability. The Shannon entropy would be about $14.3$ bits, but the min-entropy is precisely $1$.
Min-entropy can be associated with the best chance of success in predicting a person's password in one guess.
Shannon entropy is defined to equal $$\sum_{i=0}^n{-p_i\log_2(p_i)}$$ for a probability distribution $p$ with $n$ posisble outcomes. Shannon entropy describes the average unpredictability of the outcomes of a system.
It also measures how much information is in a system (on average). Shannon entropy is the smallest possible average file size for a compression algorithm designed specifically with the distribution $p$ in mind.
Max-entropy is defined solely on the number of possible outcomes. It is equal to $-\log_2(n)$. It's not particularly useful in cryptography or passwords. It's a measure of the number of bits you would need to have to designate one bit pattern for every possible outcome.
The three quantities are always the same for a uniform distribution. This is because $p_i = p_\text{max} = \frac{1}{n}$.
$$-\log_2(p_\text{max}) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$
$$\sum_{i=0}^n{-p_i\log_2(p_i)} = n(\frac{1}{n} \log_2 (\frac{1}{n})) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$
This is why passwords picked from a uniform distribution (using a secure RNG) are said to be stronger than human generated passwords. Humans are biased in which password they choose. (Their password distribution is non-uniform.)
Entropy is a measure of fundamental information within a system, and comes in various degrees of conservatism as far as cryptography is concerned. But there is a very important threshold entropy measure called Shannon entropy.
You hint at it in your question, in that no entropy measure lower than Shannon entropy can completely describe a system. So Shannon entropy can fully describe a system without any information loss, and forms the lower bound for any compression algorithm. Min. entropy as $-log(p_{max})$ tends to be used in cryptographic circumstances as it's the most conservative. But it cannot fully describe a system. It is a lossy measure of information. By analogy, min. entropy is to information as a JPEG is to an image. Shannon entropy would be a PNG or GIF.
And no, a password of 100 random independent bits would not have a min. entropy of 100 if you measure it empirically. A real sample of 100 random bits might easily result in 60 ones and 40 zeros. That would give a min. entropy of $ -log_2(0.6)*100 $ which is 74 bits. That's why it is called min.
The following shows this min. effect on a histogram of bits from /dev/urandom:-
Empirical min.entropy in this case is 0.9913 bits/bit of the sampled 1MB of data, whereas you might theoretically expect 1.0 bits/bit.
