There's a handful of ways you can accomplish this. Here are some:
Infrastructure: Establish a SSL/TLS-enabled VPN with your client. Use the new private network to connect to your client's network. Pro: Little to no change in code, depending on your current implementation. Con: Depending on your client's infrastructure (and yours!), it may not be possible.
SSL: Establish a direct secure socket layer connection between the client and your server. Pro: Easy to implement. There's an example on CodeProject about how to implement it via MS SSPI SSL and OpenSSL you can use as a base for your own implementation; here's the link. Con: SSL have some well-known security issues you should know about before considering implementing it.
Common algorithms (AES, DES, Triple DES, Blowfish): Internal implementations you may use before sending and after receiving packages on your communication layer. Pro:Loads of libraries publicly available, some natively available since .NET 3.5 and up. Con: As you mentioned, some may be overkill.
Custom algorhythms: Create your own! Give those bits a shake. Pro: It can be as light as you want; public available cracking tools would be near useless. There's an example here of a simple custom encryption protocol for 32-bit integers, easily adaptable for larger content. Con: Public algorithms are thoroughly tested and validated, and do ensure a level of security that your implementation may not meet; there's little valid reasoning for reinventing the wheel.
You may, of course, mix two or more if you want extra security (for example AES-encrypted content over an SSL connection), but it's up to you to decide.