En electrónica e informática existe la "Ley de las 2 Bes":
Si es Bueno y Bonito, no puede ser Barato.
Si es Bueno y Barato, no puede ser Bonito.
Si es Barato y Bonito, no puede ser Bueno xD
Dicho esto te recomiendo un teléfono con Symbian, estilo 6630 o 6680, estos están bastante bien de precio, tienen muchas posibilidades, y admiten tarjetas de memoria para meter lo que quieras. En mi caso tengo instalados programas para mp3 (Jukebox) y DivX (SmartMovie) que son mucho mejores que los que incluía el movil. Muy práctico para los viajes o las esperas. Un par de capis de Stargate en alta calidad vienen a ocupar 240Mb. Además las RS-MMC están tiradas de precio.
El Sony Ericsson W810i (creo que era) tampoco está nada mal y cumple con todo lo que tú pides con creces, pero es mas caro.