The Symbian operating system evolved from EPOC. EPOC was the operating system on the Psion PDAs that were quite popular in Europe but never seemed to catch on in North America. At the time PalmOS was really the PDA platform for North America. Symbian has done a nice job of integrating with phone functionality. Nokia seems to be able to make a good phone and integrate it with a reasonably good PDA.
I had a Treo 700p for a while. Before that a few other palm devices, and one of the old Treo 180s. The Treos just aren't that great as phones. Partly poor RF performance and poor audio quality really ruined otherwise nice devices.
RIM is another serious contender. Their operating system and Java based applications actually can do quite a bit more than many would expect from a few years back. The operating system is fairly stable and can multitask. Obviously it is oriented towards messaging, but the selection of applications is actually quite impressive. The UI design on the RIM devices is simply fantastic - the things are quick and easy to use. There is a reason these things are so popular.
and, of course, there is Windows Mobile. There's a lot of complexity there. I'm not a fan, but some people like it.
My advice, if you want a good phone with PDA functionality, Symbian is probably a good fit. If your focus is on messaging applications and you also need a device that functions well as a phone, then look at RIM.