Ubuntu Multimedia :: Converting Entire (sub) Directories Of Video

I have a collection of music videos of various ages, and want to consolidate the codecs into mp4 files with the following criteria:

1) Retain the same directory structure and same name, hopefully with something like "/music/Videos (Encoded)/" and "/music/Videos (Failed Encoding)/" (Note: Using UTF-8 filenames)

2) Prefer to do this all in one batch; terminal commands/ bash script = awesome

3) Keep the highest quality video without having to encode everything the same (some widescreen, some hd, some with super low resolution)

4) Retain the audio stream untouched (plus, some help on what command to do to convert it to a good format) and, hopefully, to encode with settings that allow for universal apple playback (Handbrake as a great preset for this)