[For the full tutorial including MediaCoder setup, scroll down past the settings list.]

After much trial and error, these are the settings I've used to successfully convert my movies and videos for playback on the S390G. If you already have a preferred video converter, just use the following settings. Might need a little tweaking according to your specific converter, though. This phone also has a bug: if video files are larger than 256 MB (~1:42:30 with my settings), playback past this point will begin stuttering, and eventually terminate with an error message.
WORKAROUND: You'll need to split any movies longer than 1:42:30 into segments to avoid this.

Container: MP4
Codec: H.264
Software Encoder: x264
Profile: Baseline
Level: 5.1
Preset: Medium
Tune: Film (or whatever you're transcoding)
Reference Frames: 10
Rate Mode: 2-pass
Video Bitrate: 256 Kbps

Format: LC-AAC
Sample Rate: Original from source
Target Bitrate: 96 Kbps

Now, for the full tutorial...
1. Download MediaCoder - choose the version that is appropriate for your machine.
2. Unzip and install by clicking on the setup file. Make sure anything you want to include is checked.
3. After install finishes, run MediaCoder. A splash screen will display; don't go to the first time configuration wizard, just click the button that takes you to the main screen.
4. Set your output folder in the upper right hand corner of the screen (this is where your videos will end up after converting).
5. Click on “Video” tab in lower left of screen. Set Video Bitrate to 256 Kbps, Rate Mode to 2-pass, Format to H.264
6. x264 should have automatically been selected as the encoder. If not, select it, then on the right side, under “x264” tab, set Profile to Baseline, Level to 5.1, Preset to Medium, Ref. Frames to 10. Tune should be set to whatever you're converting.
7. Click on “Audio” tab in lower left of screen. Make sure Enabled is checked. Set Format to LC-AAC, Resample to Original. Make sure Auto Select is checked beside Encoder and Source.
8. On the right side, under “Nero Encoder” tab, set Rate Mode to Target Bitrate, and set the Bitrate to 96 Kbps.
9. Proceed to “Container” tab; select Container to be MP4.
10. Proceed to “Picture” tab; check Resize and set to 320x240, make sure Aspect Ratio is set to Keep Pixel AR, set Crop to Crop to Fit.
11. In the next tab, “Sound”, Channels should be set to Stereo. If you feel the audio is too soft after transcoding, you can activate the Gain and increase the volume in this tab.
12. Proceed to “Time” tab; this is where you can split the video if longer than 1:42:30. Unfortunately, Split function is disabled right now, so you'll need to transcode those movies 2x, setting the Start Position and End Position appropriately to split into 1:42:30 length videos (or I just split into 1:40:00 segments).
13. If you wish to include subtitles, go to “Subtitle” tab to do so.
14. If you have an SSD like me and don't want MediaCoder to be writing to it during transcode, set the temp folder by going to File->Settings->Overall->Task->Working folder and changing it to a directory of your choice.
15. Your settings are now complete! To save them to be able to load later, go to File->Save as Preset.
16. Add video files to the queue by clicking “Add” button and navigating to your videos. “Add Folder Recursively” will add all videos in a folder AND its subfolders, though it's been flaky in my experience.
17. Finally, click “Start” button and let it do its thing! MediaCoder WILL by default consume 100% of your CPU as it transcodes, so it's best to do your converting when you're not using your PC. Also, about every 10 files a window will pop up asking for donations. The conversion will continue after 60 minutes, so just be patient or make the donation if you want to support the author.
18. Enjoy glorious H.264 video on your S390G! If you get “File has invalid contents” at first, just keep clicking play – it will eventually work.

Hope this tutorial has helped, and thanks for reading!