I like my webhost very much but find that the addressbook software for my e-mail program is very limited. I found a program called "Turba" that is an add-in to Horde. I sent my webhost an e-mail and asked them if they had it on their server and this is part of their reply:

"You would not have the access to add that to our installation of horde but you are more than welcome to install your own copy of horde to your webspace and install Turba onto your installation."

This sounds great BUT.... I am still a Linux lookie-lookie. I don't know how to install software. Is this something that is likely to get over my head?

It's not trivial, but not brutally hard either.
The hardest part is making sure you have all the deps you need installed (which if horde is already installed is likely)

You should probably talk to your host again and see if they can't tell you how to best go about this.
If you have more specific questions feel free to ask.

I have already asked my host if they would install it for me but they said they don't do that.

Right, but will they not give you some advice on how to install it yourself? Installing on your own computer is easy, but since this is a webhost you will not be able to install using a package manager, or from source (unless your webhost gives you access to a C compiler, doubtful).

The point is that there is little help we can give without knowing the webhosts setup, and this you will have to get from them. I suggest you give them a call again and find out how and where to install it, then if you have more specific questions you can ask us...