You want either xml or json over http. Web Services and REST over http was created for interoperability problems between different platforms which is what you're facing.
Since you're using C# for the server, you can look into WCF and use either a REST pattern or SOAP (web services) to expose your actions and data. Concerning the data you can serialize those objects over the wire as JSON or XML.
For iPhone consumption, I would recommend REST (since that basically maps a url request path to a C# method). From the phones perspective, it's just a url request and xml or json data comes back.
In C# you simply create your methods and decorate them with DataContract attributes. Then, on your methods you map them to url relative paths. Search the net for WCF and REST services. You can run it in any host from a command line to a windows service to IIS.
http://msdn.microsoft.com/en-us/library/bb412178.aspx
When creating those C# services, if REST, you can hit the requests in a browser and see the data come through. You should also look into Fiddler to inspect your traffic: http://www.fiddler2.com/fiddler2/
On the phone side, you first need to make the http request. You can do that with iOS classes but wrappers like ASIHTTPRequest make it much easier. Once you get the response back, you have to parse it. If you choose XML the iOS classes offer simple ways to parse the xml response. If you choose JSON, there's classes like SBJSON.
http://allseeing-i.com/ASIHTTPRequest/ - (Read this ASIHTTPRequest blog before using)
https://github.com/stig/json-framework
rest web services in iphone
There's also a much higher level framework called RESTKit which makes the iPhone side much easier.
https://github.com/RestKit/RestKit
Hope that helps tie it together for you.
EDIT:
Adding the create new user scenario:
The client creates a user object with the data (username, password etc...) and sends an HTTP PUT request to http://yourserver/myservice/users. The client serializes the user object to JSON/XML in the body.
What is the recommended/effective request payload for a REST PUT method?
PUT vs POST in REST
The server receives the request. On the server, you have a WCF "myservice" service (it's a class). It has a "public User CreateUser(User user)" method. In that method it creates a user object by doing whatever it has to do (call database etc...). It returns the User object because perhaps the server added info like the user id. The article below has a put request example.
http://damianm.com/tech/building-a-rest-client-with-wcf/
The client would get the response and the user object with all the details like id, etc... would be in the body as JSON/XML. It would deserialize that into a User object on the phone.
The server could also expose things like:
/User/{id} --> public User GetUser(string id);
