Im no PDA expert, but I am also looking to get one in the next month or so.
The best ive seen so far is the Compaq Ipaq.

http://athome.compaq.com/showroom/st...paq-athome.asp

Afew different models to choose from, color screen, loads of expansion and heaps of features.

Not sure about movies and MP3s but since it runs Pocket PC 2002 it sure wouldnt suprise me if it was possible.

Let me know which one you decide on so I can have a look for the best options.

Cheers

Simo