There are several things to consider with the conversion of PSX movies.
1) PSX video converter
The PlayStation could run in two graphics modes: 24-bit or 15-bit. Most games (including FF7) used 15-bit. So all the movies are displayed with that lesser color depth. Additionally, the PlayStation (and all emulators) use very fast video decoding methods that sacrifice quality for speed. Using any of the direct converters out there will definitely produce better results than capturing the video in play.
The PlayStation movie data is stored on the disc in a (slightly unique) YUV format. jPSXdec is the only converter that takes advantage of this and performs the least amount of operations on the data by outputting YUV directly (all other converters add the additional operation of converting to rgb). Ultimately we need the data in a YUV colorspace anyway. YUV may also let other video processors perform magical mathematical operations on it in ways that can't be done on just rgb. (I just need to figure out why the colors are coming out differently ;)
2) framerate
Due to limitations of the video formats on PlayStation discs, frame rates often fluxuate slightly during play. This fluctuation didn't exist in the original movies rendered by Square. So which is more accurate: the movies Square made, or the movies you actually watch when playing the game?
For FF7 specifically, I'm pretty sure all the movies originally had a half-NTSC rate of 15000/1001. However only the videos with sound were played back (approximately) at that rate (and probably only because the audio would get out of sync otherwise). Videos without sound were played back at exactly 15 fps.
Note that an upcoming option in jPSXdec will let you output exactly how it is rendered on the PlayStation (or at least my best guess ;).
3) how the audio & video sync
Also due to the PlayStation limitations, audio and video may not have synced up exactly how the original master did. I'm curious now how the PC FF7 videos sync the audio and video. That might give some insight as to how we might want them to sync as well.
4) scaling algorithm
Not very familiar with these technologies, but it sounds like NNEDI2 may be the way to go. I also wonder if there are any other filters worth running the videos through (
an example of what filters can do to improve quality).
5) final format
h.264 is pretty much the best quality codec available these days (just ask google to compare xvid and h.264).
6) how to encode
I'm not familiar with any other free h.264 encoders other than ffmpeg. Even the SUPER converter is actually using ffmpeg under the hood (it just provides a pretty interface). The hard part is experimenting with various qscales and/or bitrates to determine the best quality:size ratio.