I've created an open source application for iPhone OS 3.0 that shows how to use REST & SOAP services in iPhone application, using XML (using 8 different iPhone libraries), SOAP, JSON (using SBJSON and TouchJSON), YAML, Protocol Buffers (Google serialization format) and even CSV from a PHP sample app (included in the project).
http://github.com/akosma/iPhoneWebServicesClient
The project is modular enough to support many other formats and libraries in the future.
The following presentation in SlideShare shows my findings in terms of performance, ease of implementation and payload characteristics:
http://www.slideshare.net/akosma/web-services-3439269
Basically I've found, in my tests, that Binary Plists + REST + JSON and XML + the TBXML library are the "best" options (meaning: ease of implementation + speed of deserialization + lowest payload size).
In the Github project there's a "results" folder, with an Excel sheet summarizing the findings (and with all the raw data, too). You can launch the tests yourself, too, in 3G or wifi, and then have the results mailed to yourself for comparison and study.
Hope it helps!