Pues lo primero que te recomiendo es que pienses primero en las necesidades/usos que esa persona le va a dar al movil.
Es evidente que un teléfono en plan reproductor como muchos Sony-Ericsson no vale la pena si ya tiene un MP3, uno con cámara de 3MPX no tiene sentido si ya tiene una cámara en condiciones o un Nokia N95 8GB no es lo más adecuado para alguien que solo lo usa para mandar SMS. Claro que estas características como "accesorias" de un teléfono que si le pueda gustar pues nunca están de más, pero que no te coman el coco en la tienda con mil polladas de características que posiblemente ni ellos entiendan o sepan usar: pilla el que veas que le va a gustar y le va a dar uso.
Luego ya sobre marcas, yo tiendo a huir de los Sony Ericsson porque todos los que ha tenido gente de mi entorno han salido malísimos, además que la tarjeta de memoria que usan es la Stick Micro, que no es precisamente barata. Los Samsung y LG al parecer tampoco salen excesivamente buenos, y de Motorola, pues depende, algunos como el V3 es lo peor que se ha podido fabricar en años.
Edit: por cierto, si tú tienes Vodafone o Movistar, mirate el catálogo de puntos porque (salvo rarísimas excepciones) siempre te va a salir más barato que comprar uno libre por pocos puntos que tengas.