Since our launch we've used three live chat softwares:
ProvideSupport
Kayako LiveResponse
LiveZilla
We really liked all of them but so far LiveZilla is our favorite. For something that is completely free to use and customization it definitely out beats the other two. The fact that it is a free solution is just a mere bonus for us. Out of the 3, Kayako LiveResponse was probably our least favorite.
Livezilla's good as long as your comfortable including all the server coding/database needed to run it. There are more than enough external providers as well; just depends where you want the db to reside.
I'd vote for LivePerson and Kayako's Live Support suite. They've got all the features you would need and are really user-friendly, especially LivePerson.