Depends on the protocol.
If the service requests are in the clear (http), then you might want to consider a secure (https) logon transaction, which gains you a limited-time token to authorise future requests (a session cookie, in effect). Then at least eavesdroppers don't get credentials that work forever, just for a limited period.
Likewise even if the logon transaction isn't secure, at least if it only happens once it's slightly harder to eavesdrop. It's also slightly harder to use.
If you don't care about security, I wouldn't even use a username/password, just an API key. Amounts to the same thing, but if the user doesn't choose it then at least it won't be similar to any of their other passwords, so it doesn't affect anything else when it's stolen.
If you care about security sufficiently that everything is done over https, then it doesn't really make a lot of difference what identification mechanism you use, AFAIK. So do something simple.
Finally, you might care about the security of the authentication, but not about the secrecy of the requests themselves. So, you don't mind eavesdroppers seeing the data in flight, you just don't want them to be able to issue requests of their own (or spoof responses). In that case, you could sign the requests (and responses) using a public/private keypair or a shared secret with HMAC. That might (or might not) be easier to set up and lower bandwidth than SSL. Beware replay attacks.