A couple things to note: first, the "High-Definition" in HD video relates to the picture resolution, not the video compression bitrate. Indeed, a 720p HD video is still called a High-Definition video whether it is severely compressed to the point of unwatchability or totally uncompressed. (Most of the HD video I find on the net has a bitrate lower than DVDs!)

Second, the resolution of an LCD screen is fixed. If your screen has 854x480 pixels, you will be watching video at 854x480 resolution. A 720p (1280x720 pixel) or 1080p (1920x1080) video shown on this screen will obviously have to be down-scaled, or you'll only be able to see one corner of the picture at a time. Similarly, a 640x350 video will have to be up-scaled, or you will be seeing a tiny picture on just a part of your screen. All this down-scaling (or up-scaling) wastes CPU power (or whatever hardware you are using), and must naturally distort the native video to some degree.

What you want is a maximum quality picture with minimum distortion. Simply cramming data onto the machine that is inevitably going to be thrown away during the down-scaling process is not the best way to do this. The best way is to use a video encoding system to re-encode a high-resolution, low compression source video into the native resolution of your device at the lowest compression level (or highest bitrate) that your device can handle.

Again, I use handbrake for this. I use it both for the HD videos I get from the net (high-res, but heavily compressed) and for my library of DVDs (standard-def, but low compression), to squeeze the best quality I can get out of my source material before transferring it to the phone. Because Handbrake doesn't have to try to decode and re-scale the video in real time, and gives you fine control over the bitrate it will use, it can produce a video optimized for the phone that will, in fact, surpass the quality you would get by trying to run the native source video on the device.