Can I import videos that are already compressed using the Theora codec?
And if so, will Unity bother recompressing it?
Yes, this should be possible. If you have a theora encoded video packages as an .ogg stream, you should be able to just drag the ogg file into your assets folder and use the video without recompressing.
In result you target file will have extension *.ogv.