Yahoo
Here is the Yahoo Contacts API: http://developer.yahoo.com/social/contacts/
You would call into their REST API, and provide a YQL Query. It returns JSON. A JSON library is built into the latest iOS SDK.
LinkedIn
Similarly, LinkedIn has: developer.linkedin.com/documents/linkedin-api-resource-map
The LinkedIn API seems to be returning XML, so you'll need an XML parsing library.
This is a great description and comparison of various available XML parsing libraries: raywenderlich.com/553/how-to-chose-the-best-xml-parser-for-your-iphone-project . If you're not sure, go with a DOM parser -- it is more intuitive to me at least. I hope you remember how to traverse trees.
Hotmail, MySpace, others
Look for REST APIs -- these are generic web based APIs that will work with any client. You can do server-to-server communication, as well as client-server communication (both in-browser (JS) and native apps).
Now that you have this data in memory
You can iterate through it, and add contacts to your iOS device using the Address Book API:
developer.apple.com/library/ios/#DOCUMENTATION/ContactData/Conceptual/AddressBookProgrammingGuideforiPhone/Introduction.html
By the way, what's MySpace?