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.
Wait, my 2yrs old n900 can now play 720p videos and n9 can't? That's kinda hilarious, isn't it?