What is the difference between maximally entangled and maximally mixed states?
Suppose we have two Hilbert spaces $\mathcal{H}_A$ and $\mathcal{H}_B$. A quantum state on $\mathcal{H}_A$ is a normalized, positive trace-class operator $\rho\in\mathcal{S}_1(\mathcal{H}_A)$. If $\mathcal{H}_A$ is finite dimensinal (i.e. $\mathbb{C}^n$), then a quantum state is just a positive semi-definite matrix with unit trace on this Hilbert space. Let's stick to finite dimensions for simplicity.
Let's now consider the idea of a pure state: A pure state is a rank-one state, i.e. a rank-one projection, or a matrix that can be written as $|\psi\rangle\langle \psi|\equiv\psi\psi^{\dagger}$ for some $\psi\in\mathcal{H}_A$ (the first being the Dirac notation, the second is the usual mathematical matrix notation - since I don't know which of the two you are more familar with, let me use both). A mixed state is now a convex combination of pure states and, by virtue of the spectral theorem, any state is a convex combination of pure states. Hence, a mixed state can be written as
$$ \rho=\sum_i \lambda_i |\psi_i\rangle \langle \psi_i|$$ for some $\lambda_i\geq 0$, $\sum_i \lambda_i=1$. In a sense, the $\lambda_i$ are a probability distribution and the state $\rho$ is a "mixture" of $|\psi\rangle\langle\psi|$ with weights $\lambda_i$. If we assume that the $\psi_i$ form an orthonormal basis, then a maximally mixed state is a state where the $\lambda_i$ are the uniform probability distribution, i.e. $\lambda_i=\frac{1}{n}$ if $n$ is the dimension of the state. In this sense, the state is maximally mixed, because it is a mixture where all states occur with the same probability. In our finite dimensional example, this is the same as saying that $\rho$ is proportional to the identity matrix.
Note that a maximally mixed state is defined for all Hilbert spaces! In order to consider maximally entangled states, we need to have a bipartition of the Hilbert space, i.e. we now consider states $\rho\in\mathcal{S}_1(\mathcal{H}_A\otimes \mathcal{H}_B)$. Let's suppose $\mathcal{H}_A=\mathcal{H}_B$ and finite dimensional. In this case, we can consider entangled state. A state is called separable, if it can be written as a mixture
$$ \rho =\sum_i \lambda_i \rho^{(1)}_i\otimes \rho^{(2)}_i $$ i.e. it is a mixture of product states $\rho^{(1)}_i$ in the space $\mathcal{H}_A$ and $\rho^{(2)}_i$ in the space $\mathcal{H}_B$. All states that are not separable are called entanglend. If we consider $\mathcal{H}_A=\mathcal{H}_B=\mathbb{C}^2$ and denote the standard basis by $|0\rangle,|1\rangle$, an entangled state is given by
$$ \rho= \frac{1}{2}(|01\rangle+|10\rangle)(\langle 01|+\langle 10|)$$ You can try writing it as a separable state and you will see that it's not possible. Note that this state is pure, but entangled states do not need to be pure!
It turns out that for bipartite systems (if you consider three or more systems, this is no longer true), you can define an order on pure entangled states: There are states that are more entangled than others and then there are states that have the maximum amount of possible entanglement (like the example I wrote down above). I won't describe how this is done (it's too much here), but it turns out that there is an easy characterization of a maximally entangled state, which connects maximally entangled and maximally mixed states:
A pure bipartite state is maximally entangled, if the reduced density matrix on either system is maximally mixed.
The reduced density matrix is what is left if you take the partial trace over one of the subsystems. In our example above:
$$ \rho_A = tr_B(\rho)= tr_B(\frac{1}{2}(|01\rangle\langle 01|+|10\rangle\langle 01|+|01\rangle\langle 10|+|10\rangle\langle 10|))=\frac{1}{2}(|0\rangle\langle 0|+|1\rangle\langle 1|) $$
and the last part is exactly the identity, i.e. the state is maximally mixed. You can do the same over with $tr_A$ and see that the state $\rho$ is therefore maximally entangled.
See the following examples:
$\rho_1 = \frac{1}{2}(|00\rangle + |11\rangle)(\langle 00| + \langle 11|)$ is a maximally entangled state.
$\rho_2 = \frac{1}{2} (|0\rangle \langle 0| + |1\rangle \langle 1|)$ is a maximally mixed state.
The difference is not related with "maximally". Your question can be changed to :
What's the difference between "entangled" and "mixed"?
Simply speaking: "entangled" is a relationship between two systems (or subsystems) while "mixed" is a property of one system.
When the state space for a system can be expressed as a tensor product of the state spaces of individual components of the system, an entangled state is one that can't be expressed as a tensor product of states of those individual components. Thus an entangled state is a particular type of (pure, i.e. non-mixed) state.
A mixed state, by contrast, is a probability distribution over pure states. This makes perfectly good sense whether or not the state space decomposes as a tensor product.
So an entangled state is a mixed state only in the degenerate sense that the probability distribution is concentrated on a single point. Of course you can also have a non-trivial mixture of entangled states.