You can install ubuntu-restricted-extras from the Software center. This installs all the non-free codecs for almost everything.

Example: H.264 video + stream copied audio in Matroska

ffmpeg -i input -c:v libx264 -crf 23 -preset medium -c:a copy output.mkv

Anything WMV is a joke. H.264 video via the encoder libx264 is your best bet right now. While H.265 looks good on paper the implementations just are not quite there yet for typical usage (unless your time is cheap because it is slow).

You basically only need to change -crf and -preset:

• Use the highest -crf value that still gives an acceptable quality. Range is a log scale of 0-51. 0 is lossless (huge files). Around 18 is considered visually lossless. 23 is default.

• Use the slowest preset you have patience for. They are: ultrafast, superfast, veryfast, faster, fast, medium [default], slow, slower, veryslow, placebo (ignore placebo; it's too slow for any potential significant advantage over veryslow).

• Now use the same -crf and -preset for the rest of your batch of videos.

The audio is being stream copied instead of re-encoded because the vast majority of data will be video.

With all of that, I must point out that 25G is small and storage is cheap. If I were in this situation I'd probably just keep the original videos and not bother with re-encoding. Also, re-encoding may not help if the originals were encoded properly with a modern, efficient format.

Also see

FFmpeg Wiki: H.264 Video Encoding Guide