The 'typed' issue is that the class will be redefined on the client's side.
You can however get the entity collection as a datatable, use the GetMultiAsDataTable() method of the entity collection. You can then add that table to a dataset and return that dataset.
The problem is that Microsoft screwed up with the IXmlSerializable interface implementation: it always thinks the data is stored in a plain dataset, when it comes to complex types OR it sees it as a simple type. For example, I can implement IXmlSerializable on the Entity class, then produce XML in the WriteXml() method, and the XmlSerializer object will still think it's a dataset. This is fixed in Whidbey but that's not available now.
Bottom line is: if you want to offer a service to a wide range of clients, probably not .NET, use Webservices, but use pure XML, not types like MyComplexClass. If you want to offer a service to just .NET clients, use remoting.
I'm almost done with the code for a full XML serialization cycle so you can export a full class hierarchy to XML, return that, and reconstruct the complete class hierarchy using the XML at the client. That code will be ported back (it's now in Adapter) to SelfServicing once Adapter is gone gold. But that's also not available now, so the workaround today is you can serialize to SOAP, return the string, or fetch in a datatable, add it to a dataset and return that. But it's not solid, due to the hardcoded codepaths for datasets in xmlserializer, which is ALWAYS used in a webservice: the returned type is transformed into XML, that XML is transformed into SOAP, and that is transported. At the client, this SOAP is deserialized to XML and that XML is deserialized to an instance.