1) Theora encoding is not threaded (unlike h264). On an i5 Intel it would take at around 1 min 30 sec of real time per minute of video, but it depends on quality settings. For 5 minutes it would take 7 min 30 sec to convert.
2)
https://en.wikipedia.org/wiki/Theora#Performance
mpeg4 video would not be better than Theora.
3) No, not unless the patent holders ask for royalty, which none of the popular codecs do (mpeg4, h264).
4) If you are dealing with a lot of videos to transcode, then yeah you might need it.