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.
Good luck!