What is the fastest way to share data structures between Java and C#? I want something where I can literally send a "car" object or a "foo" object and have it serialized and deserialized on both server and client.
You might be able to use IKVM, it's a Java-like environment on top of .NET; you could use Java serialization on IKVM and use interop to use the objects from "regular" .NET languages.
It looks like the IKVM seems like a good idea. But if that doesn't meet your needs especially since it is still in development. However, Uri's post points you in a good direction with the use of xml and passing messages, which can be built back together on either side.
Would you be able to use a SOAP web service on the server and have the client consume the web service? The object's data structure would be described in the WSDL for the web service.
WSDL (SOAP) is fairly interchangeable. If you want something less chatty, anything like Google's "protocol buffers", "ICE" (ZeroC), etc offer interchangeable binary serialization and code generation.
For .NET / C#, there are currently two viable protocol buffers implementations here; protosharp is essentially inactive and incomplete) - either would be fine, but neither currently has a complete RPC stack, so you'd have to handle message passing yourself.