BeeJive - definitely. I've used many IM apps, and BeeJive is the one that runs the smoothest and most like their larger computer like counterparts. My only dissappointment with BeeJive was their lack of a Storm version... the beta still bites.
I did a trial on both and purchased BeeJive in the end. I like how it allowed me to jump around the menu quickly by typing just the first letter of each item I wanted to select. I also like how it sorts my accounts.