Progressive Scan is not as important as retailers make it out to be. Progressive scan outputs 480p instead of 480i to the TV. If you have a HDTV, most of them have line doublers to upconvert a 480i to 1080 which is HDTV resolution. So I really wouldn't worry about progressive scan. Buy your DVD player from a place where you can return it and try it on your TV. If it looks good, keep it, if not return it and try another model.
To buy the best cheap DVD player, you need to make sure it supports the best connection that your TV has (DVI, Component, S-Video, Composite, ANT(Coax)) from best to worst. If your TV has S-video, make sure your DVD player does as well. If you have a basic low-end TV, almost any DVD player is fine.