Too bad about the quality of those conversions. I'm assuming you don't have the original 8mm film anymore, as depending on the grain size (more-or-less directly related to the film "speed" or ISO value) and whether it's black and white or color film you should be able to get anywhere from a crisp 720p to a 1080p resolution when scanning it, it'd avoid a lot of the loss of midtones you see in the video you linked.
If all you have are the VHS tapes you could try getting them converted by a different company, or doing it yourself. The flickering looks a lot like a VHS player not doing brightness correction correctly to me. The original film wouldn't have flicker, The film scanner would be unlikely to introduce it. A VHS player needs to do brightness correction on the signal it reads from the tape in any case since the signal strength may vary with tape age or wear, or even the signal strength at time of recording. A VHS player would normally use the sync pulse to detect how much it needs to amplify the signal, if that mechanism gets out of whack you can get wild brightness fluctuations. Some of the color could probably also be rescued if the VHS conversion was done more carefully.
If you don't have the VHS tapes anymore either (which is a perfectly reasonable thing after having them converted) you could still probably get a lot of the brightness fluctuations out by editing the avi files. I don't know of the top of my head any tool that'll do brightness equalisation like that automatically but I'm sure it exists, it's computationally not a hard problem. You'll probably not be able to recover much color from this stage though, the signal is thoroughly quantized once it hits the digital realm and no amount of fiddling will get you any more color resolution though you might be able to correct it a small amount with some color correction.
In all cases you're best off getting as close to the source material as possible, but I'm sure that even if the digital copies are all you have you can get it to a place where it's at least watchable.