No one has replied to this, but I've worked out the answer to my own question, so I'll post it here in case it winds up being useful to someone else who might search and find this topic.
It seems that to create new content with the basic soap API, you need to first execute the update operation from the RepositoryService passing CML to create the "contains" association from the parent folder, and then use the write operation of ContentService to give it actual content using the Reference returned from the update operation.
I should note that I'm using Java, and am not using the alfresco-web-service-client jar–there's no need to take on all that baggage if you already know how to and have your own infrastructure to do your own web services client set up and generate classes from the WSDL, though the source code to this jar in the alfresco SDK, along with the samples that use it, is useful for figuring out how it is used. The createNewContent method in the class org.alfresco.sample.webservice.ContentReadAndWrite was the key to my getting this working, and while that code uses the client jar, the code is not so different without it.
It would have been nice if the web services documentation had spelled out that this really basic content operation required this combination of 2 web services operations.
Another point of confusion that the documentation could have prevented, is the dichotomy between commands that are directly on the web service object and commands that in CML.This CML basically creates a whole additional set of operations buried inside some of the web service operations. It's just several more operations which instead of being actual web services operations directly, are structures passed in. Personally I don't find this arbitrary dichotomy very handy, it just complicates the API. In any case, it would have been nice to draw attention to the fact that some of the basic content management operations your going to want to perform with this API are on the service objects directly, and some are "hidden" inside this second command syntax in the CML (which can be constructed largely by constructing instances of the WSDL generated types).