I highly recommend writing a JPEG en/decoder as an exercise in coding; getting to the point of being able to decode almost all the images you probably have or can find on the Internet shouldn't take more than a few hours and <1k lines of (C) code. Once you've done that, you'll be ready to take on a simple video codec, like H.261. I find it self-motivational because the results are very visible (and if you have a bug, all sorts of fun effects can appear too.)
(As you may have guessed, I've written a JPEG decoder, as well as JBIG2 (partially), H.261, and MPEG-1, each of which is roughly 1kLoC. Currently thinking of trying JPEG2000 too, which is over an order of magnitude more complex.)