For information theory, a really recommend: Thomas M. Cover, Joy A. Thomas "Elements of Information Theory" - it starts elementarily, has direct examples, straightforward definitions and readable notation.

(And first recommendation by Cosma Shalizi: http://vserver1.cscs.lsa.umich.edu/~crshalizi/notabene/infor...)