I wouldn't say it's gentle but it certainly is a great book. Great exercise problems. Some of the proofs are so elegantly done, especially the way calculus of variations is avoided.
David Mackay's book hand holds a little more than Cover and Thomas, although it's remit is more than just information theory.
