What I am trying to accomplish is to be able to use List<>.Contains() using the custom data structure(s) returned by the WCF service.
I implemented the IEquatable<>.Equals but it's not really working on the client side. Contains() always returns false. I am wondering if the Contains() method is actually part of the class when it's put together on the client side.
No this will not work. Actions like implementing IEquatable<T> is adding behavior to a type. Data contracts are only meant to specify data, not behavior. Behavior will not be copied down when the client adds a reference to your type.
No. Web services are generally meant to be platform-agnostic, so they define things like operation contracts (for operations performed on the server) and data contracts (for exchanging objects composed of simple data fields). But they don't define methods on objects as this would require knowledge of the client-side platforms. (For example, how would you marshal your IEquatable<>.Equals IL code to a Mac client?)
What you can do, if you have full control over your WCF service's clients, is deploy the same library to both the clients and the server. That is, you could put your data contract classes in Data.dll and deploy it to both the client and the server (as opposed to using the default proxy classes generated from the service contract on the client).