First, you don't "encrypt with a certificate". You encrypt with a protocol which may or may not use certificates for public key distribution. The most commonly used protocol for protecting bidirectional data channels is SSL (now known as TLS). In SSL, there is a client and a server, which need not correspond to the "client" and "server" at the TCP level: the SSL "client" is the one who begins the SSL handshake, i.e. who sends the ClientHello
message.
In SSL, the server normally shows its public key as part of a certificate. The client validates the server's certificate (it checks that it is issued by a trusted CA) and verifies that the certificate indeed contains the intended server name. This means that the client has some guarantee that it is talking to the right server. On the other hand, the server does not know who the client is; the server just has the guarantee that it is talking with the same client during the whole connection.
If the server must know who it is talking to, then some sort of client authentication must be applied. SSL supports client certificates for that. Another method, very often employed in a Web context, is to have the client show some credentials (a login and a password) inside the SSL tunnel (since the client has some guarantee that it talks to the right server, then it can send the password to the server without fearing interception by an attacker).
SSL also supports some certificate-less connections, e.g. the PSK cipher suites, in which client and server authenticate each other with regards to a shared secret value; if, in your situation, you can arrange for client and server to know a common secret key, then this will avoid all the certificate business. If the shared secret is a low-entropy value (e.g. it is a "password" that a human user will be able to remember and will accept to type occasionally), then SRP cipher suites are the way to go. PSK or SRP support in .NET may require some extra libraries, though (e.g. OpenSSL bindings for .NET).