Look out for Symbian phones. Most Nokia N or E-series phones have many different applications available that allow you to do all sorts of things with SMS. From spam filtering to conversation management and more.
I use a Nokia E90 and find that its probably the most powerful cellphone I have ever used. I have an iTouch and can't imagine trying to use it for anything beyond music/video and the occasional browsing. If the browser on my E90 isn't enough, I can use an application called Joiku Spot to share the HSDPA connection on the E90 with the iTouch via wifi, or just connect to a PC/Laptop via Bluetooth, USB or even InfraRed and use HSDPA that way.
The E-Series phones all offer a free application from Nokia called MfE (Mail for Exchange) that allows you to access Exchange 2000 through to 2007. There are other companies out there offering their own versions that offer even more feature than the basic MfE from Nokia.
There are Blackberry client for the Nokia E series phones so if you currently have push services from Blackberry, you can continue to use them on your Nokia. Probably the most significant difference would be the cameras. N-Series tend to have better cameras at higher resolutions (anywhere up to 8MP) where as the E-series average 3.2MP cameras.
Many of the phones have built in GPS and include Nokia Maps, but it also works equally well with Google Maps for Mobile. Right down to turn by turn route assistance using the GPS.
Symbian based cell phones have been around since 2001 when Nokia released the first 7650. The Symbian platform is a direct descendant of the old Psion devices. It is mature. It is stable. It has years of user feedback. It just works. There is a very large application base available for it out there.
Oh, and the best feature for me has been the version of Python Nokia released for their E and N-series phones along with an API that allows you to hook in to nearly every aspect of the phone, from the GPS, camera, OpenGL, through to pulling data from the calendar or the messaging platforms among others.
The most paranoid, yet strangely compelling, Python script I like is one that works as a kind of panic button. You load the app and it immediately takes a photo of whatever the camera is aimed at, sends a MMS message (or email, or SMS) with your current location from the cell tower while it waits till it has a GPS lock and includes that photo if possible. Once it has GPS lock, it will send GPS coords via SMS every X (edit the script to set, defaults to 180) seconds and then will also call a designated number to play back a pre-recorded message, then use text-to-speech to give the GPS coordinates on that call. It can then call emergency services and play that same message for them. If it can't get GPS lock (say you're in a building or whatever) then it will just use cell towers it can detect so that there is at least some method of tracing you.
All from a python script running on a cellphone. You can find it on the Nokia developer forums wiki. Because its a script, you can modify it to suit your needs and location if you want. Nokia's Python API is so straight forward that you can easily add features of your own.
You could probably even write a Python script to manage your SMS messages exactly as you want them to be dealt with if you know even a small amount of Python.
Good places to start are community sites like allaboutsymbian.com or my-symbian.com. Or you can check out the S60.com blogs and sites.
There are a lot of devices from Nokia now. E-series are targetted more at Enterprise users where as the N-series are more consumer market devices, but can still do everything an E-series device can do.