Pues si no eres muy exigente con el sonido (aunque a mi me parece que suena bien) me iría de cabeza a un Nokia, yo tengo el N95 de 8gb, pero te recomendaría el Nokia N85, mas robusto que el N95, pero con la pantalla mas pequeña.
Te puede valer para reproducir vídeos en divx (la pantalla es relativamente pequeña, pero cuando vas aburrido te vale cualquier cosa), radio, tom tom, cámara de 5 mpx, conexión mediante rcas a TV y muchas mas opciones que nunca utilizarás, la batería también dura bastante si no utilizas el tom tom ni el wifi, y teniendo en cuenta que la conexión de auriculares es jack normal, le puedes poner unos auriculares mas decentillos.
No es perfecto, pero a mi me parece resultón en todo, (aunque la navegación por internet es un poco tediosa) y si manejas mas presupuesto, pues un N97.

Pero cuidado, no matéis al mensajero, tened en cuenta que sólo es un teléfono.
Saludos.