Can't tell that much about brands and models, but here's some characteristics to check:
1. Video chip. 27MHz/10 bits is "enough" for handling MPEG2. Higher rates and/or more bits allows for oversampling to improve the signal.
2. Outputs. Should include the best format accepted by your TV (examples of "good" ones are RGB, Component video, DVI).
3. Progressive scan (if your TV is compatible). There are several types of PS, though. The bigger TV, the better PS algorithm is "necessary".
I have a budget multiplayer, Pioneer DV565A (DV563A in U.S.), often called "best bang for the buck" on the audio side. Video is perfectly fine for me. But then again my TV is 28" CRT, and almost every more expensive multiplayer carries superior elements, at least in theory.
I have the Denon DVD 2900 both this and the cheaper 2200 have the same video converters 12bit/108mhz and get rave reviews for picture quality especially through the component outputs.
I can vouch for the picture qualty of the 2900 but you may want consider the new models coming with the DVI and HDMI connections and even better video chips. (see the 3910 on Denon's website).
I agree with A L that that Pioneer has had good reviews - especially for the money!