Public-key encryption on microcontrollers
Erik-oliver Blaß , Martina Zitterbart.
"Towards Acceptable Public-Key Encryption in Sensor Networks". 2005.
"dsPIC DSC Asymmetric Key Embedded Encryption Library"
an implementation of RSA, Diffie-Hellman, DSA, SHA-1, MD5.
(Are such 16-bit microcontrollers in your range of interest?)
"Links to Embedded Crypto Implementations"
lists a few implementations of RSA on 8 bit microcontrollers.
"full size" symmetric ciphers on microcontrollers
Many people implement cryptography on a microcontroller very similarly to cryptography on any other CPU -- write a program to do encryption or decryption using the same ciphers we use on any other CPU.
Quite a few modern 8-bit microcontrollers have enough program memory (often called "ROM" for historical reasons, although today it's usually Flash memory) and RAM and processing speed to handle the full Advanced Encryption Standard (AES)(a)(b)(c)(d), Triple Data Encryption Standard (3DES)(a)(b), Enigma(a), RC4(a),
as well as less-known algorithms
such as Alexander Pukall’s PC1 (a).
symmetric ciphers designed for low RAM
Quite a few microcontrollers have 256 bytes of RAM or less. A few full-size ciphers work just fine, but ciphers like RC4 seem impossible to implement in this environment.
A few symmetric ciphers seem specifically designed for this environment -- KeeLoq, TEA, XXTEA, etc.
Other cryptographic techniques for microcontrollers
A few bootloaders for embedded systems use encryption.( "USB PIC Bootloader with XTEA encryption" )
Rather than doing the encryption in the CPU itself, a few systems have an external chip that does crypto stuff.
( CryptoAuthentication, CryptoMemory, Trusted Platform Module, etc. )
Such dedicated circuitry, hard-wired to perform some calculation, often requires significantly less power than a more general-purpose CPU programmed to perform the same calculation.
This way newly-introduced bugs in the software on the main CPU can't possibly leak the secret keys stored in that external chip, or introduce new flaws (new timing attacks, etc.) in the algorithm implemented in that external chip.