This is not a solvable problem, and has been discussed at length around SO. For one "hub" question that includes links to several others, see Secure https encryption for iPhone app to webpage.
Using obscurity is not a horrible thing. But keep it simple. XOR the value with some random key. Done. Putting more and more layers buy you nothing, and cost you complexity (which means time and bugs, which are the enemies of both profit and security). If someone puts a debugger on your code, they're just going to log all the data you send to the server, so all the hoops you jump through to hide how you compute the password won't matter, because eventually you have to send it to the server. So keep it simple to stop people from just using "strings" to pull it out, and recognize that you cannot stop a debugger.
The only way to secure the service-provider's key is to put that key on your server, and then proxy for the service after authenticating the user. If you put it in the code, then it is discoverable, period. If this were a solvable problem, there would be no unlicensed copies of software, no unlicensed copies of music, no jailbreaks for iPhones, etc etc etc. If Apple can't stop reverse engineering when controlling every piece of the system from the hardware to the OS, you're not going to fix it inside of an app.
What you should be thinking about is how to recover if and when the key is lost. How do you discover that it's happened? How do you expire that key and create a new one? If you're shipping the key in the code, you must assume that it eventually will be discovered, and you should have a plan for dealing with it.
As a side note, one technique I've used in the past is to download the key from our server on-demand rather than encoding it anywhere in the app. We use authenticated HTTPS and check our certificates. Of course it is still possible to fool this system (it's always possible to fool a system that gives a client information they're only supposed to use a certain way), but the thinking is at least we can change the key more easily this way to stem the tide briefly if the key leaks.