I've been through this one.
Depending on your tolerance for design some apps can be a big miss. IM+ comes to mind for me. Beejive wasn't bad but was a little cluttered. My problem with Beejive was how unreliable it was with delivering my messages. Worked really well sometimes and pretty crappy others. Believe I had a paid version, too.
A really good one to try is Verbs. I picked up the paid version for added perks and while it wasn't perfect but it was certainly reliable. It is also very clean and easy to use.
But the absolute BEST Talk app I've used is honestly Google+. So long as someone you're talking to has the app on their device it is almost flawless as messaging app. It does get a little annoying with handoffs between + and Talk proper, though. Plus you need to get people to adopt it. It is worth it if they do.
Finally, I can't speak to this one but a friend of mine speaks very highly of AIM.