I have a similar situation, just bought a 50" HDTV and noticed that in many cases the picture looks WORSE than it did on my old 27" JVC.
Part of the problem is that on a smaller screen the flaws are harder to see. On a great big screen they leap out at you.
I did a little bit of experimenting and found that the best picture (subject to the constraint of not buying a lot of expensive stuff) comes from my old (like 5-8 years) Toshiba DVD player using the component video outputs. Brand new players using DVI and HDMI produced a picture so cruddy that I returned them.
The major flaws are caused by how MPEG decoding is done. There’s only a couple of decoding chipsets out there and many of them use the same problematic code which leads to jagged edges, color problems and “blocking” or “blotching” (areas of solid color have a blotchy appearance - like a night sky or a concrete floor).
These guys have a great series of articles on this along with very in-depth ratings of how various DVD players handle the problems:
Sorry, one other thought; if there is an electronics store near you with a good return policy (many of them will let you return gear in new condition for a full refund within a couple of weeks) you can buy a player, try it out and see what works best for you.
I tried some inexpensive players from Samsung and Denon and found that the HDMI output was worse than my other choices (component, S video and even plain old composite) and none of them were an improvement over my old player, so I returned them - why pay a few hundred bucks for that?
If you do decide that HDMI/DVI is working great, check out the cable prices and shop around. The big box stores will really ream you there, we’re talking $100 for a 1m cable; more snake-oil than with speaker cables. A few manufacturers will include the cable but many don’t.