"Use" as in with your application and free to parse without needing to buy a license. Also, preferably have audio as well.

I did find Theora. Has anyone used this before? If so, what was your experience with it?

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.