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.

Found an excerpt online. Seems like a gem of a book.