Why is prostitution considered immoral, as long as it is a service that is
Kinda depends on what you think is OK to buy, sell or rent, doesn't it? We don't accept slavery, because we don't think people should be for sale or should ever be owned--though we accept that it is OK to pay for the labor that people can perform in some cases.
So I agree with the premise of your question: in general, we seem to be OK with paying for services. Is sex something that we should (or could permissibly) think of as a kind of service? Notice that such a view of sex is different from the view we take in romantic circumstances. There, we take sex to be a kind of intimacy between two people--a way of relating lovingly to one another. Prostitution, I think it is safe to say, isn't like that. It is more, as you say, like a service. But surely one could reasonably wonder whether thinking of sexual acts as services is the right way to conceive of them.
Now, as with so many ethical questions, we might find that we are led to different sorts of answers if we apply different kinds of ethical insights. Do people have rights with respect to the uses of their bodies? Well, it seems so. So why do the prostitute and john not have the right to do with their bodies as they please, given consent by both parties? Well...maybe the rights of others get engaged here, too--rights of the members of the rest of society to determine what sorts of commerce they will, and what sorts they will not, permit within their communities. So perhaps an individual's right to the uses of his or her body is only a prima facie right that might be defeated if it comes into competition with the political or economic rights of communities to regulate commerce or other aspects of social interaction...?
(I confess I am not all that good at this way of thinking, so I will allow others better at this to chime in here.)
But let's take a different tack. Go back to what I said about sexual acts as services. I'm a virtue theorist in ethics, so the way I take this sort of question is as follows: Would a virtuous person think of sex acts as services? I think not. It seems to me that an admirable human being would neither think of sex acts as services, nor would he or she wish to have others serve them in such a way. This is not at all to say that admirable human beings would abhor sex! It is, rather, to say that they would think of sex acts from a point of view that was other than that of serving or being served. So, from this point of view, there really does seem to be something wrong with prostitution--it functions on the basis of a view of sex that we would not really wish to promote, if we were seeking to encourage virtue, and one that seems to be the product of a faulty view of the value of the activity in question--a value that is not virtuously commodified.
Notice that this is not at all an argument to the effect that prostitution should be outlawed, or that it should be regarded as morally impermissible. Lots of stuff falls short of virtue that we would not outlaw or anathematize. There may even be aspects of certain kinds of sexuality that actually find sex-as-service part of the thrill.
But even so, we can fault such things on the sorts of grounds I have given, and so it seems that there is, from a virtue theoretic point of view, a genuine moral fault in prostitution (from both the prostitute's and the john's points of view) that we would not similarly assign serving as a driver or cleaner. These latter activities seem to be correctly (and thus virtuously) conceived as services. Not so, for sex--even if the idea turns you on!