this is assuming you dont want to go 3G (i'd recommend not yet as the current handsets that are 3G arent too good as yet; like bricks).
goto some highstreet store where you can actually try them out, and give them a go. there are lots that offer what you want, but some just dont look nice, and many have annoying little features.
I currently have a nokia 6230 which i'm very happy with; it just works. no flashy menu display like you'd get with a sony ericsson, but who needs that? it just does the job. does everything you want and more.
an example of an annoying feature: with my old moto v600, if i was typing a really long text message and accidentally press the "end call" button, it takes you back to the home screen. going back to the text message, its blank again! this is easier to do than you think. but it doesnt say small things like this in any guide.. you have to go and try them out.
also realise that phones with flashy displays like sony ericssons become very slow once you either:
1) leave them on for a while without restarting
2) have lots of text messages or other things in memory
this is what attracted me to the nokia; it does have a colour screen but its nowhere as good as the ones from sony ericsson or motorola. but it does the job.