You can use the WebM Project's stuff. They use the VP8 video codec and Vorbis audio codec, both of which are supposed to be free to use.
I've never used Theora or libvpx (the VP8 codec library) directly. I've only used them through FFmpeg/libavcodec/libavformat, but it's easy enough once you get over the first (fairly large) hurdles (if you're new to video/audio encoding/decoding, it takes a bit of work to get used to how things work and exactly what's needed and why). I've been pretty happy with VP8 and Vorbis (quality/size wise), and I like/am comfortable with FFmpeg.
I didn't realize this was such a tumultuous legal issue... I knew generalized patent laws were out of hand but this is just absurd.
I'm surprised someone hasn't patented breathing. We can only hope that big-business money mongers will eventually realize
that inhibiting progress like this is just shooting themselves in the feet.
FYI: Bink is really easy to implement, I recommend it if you've got the $8,500 in your budget.