Based on the requirements you listed, I think an XDA II is the only thing that would fit the bill. It's a Pocket PC Phone Edition, so you can make calls with it, you can play movies and mp3's, and it has 128 mb ram. It also has Bluetooth, not WiFi, so you can use it with a Bluetooth headset, Bluetooth GPS, etc.
Pocket PC Dubai
has an excellent review
of the device that includes links to places to buy.