This is a really big problem, and much more data is needed before rushing in to algorithm selection. I'm going to offer some suggestions, but I expect a good answer for you will need more focus.
First, public key cryptography is good for key exchanging between parties where there's an outside establishment of trust. Public keys can be delivered on certificates, and certificates can be validated against a trusted root certificate issued by a certificate authority. But as you've noted, this can take a lot of bandwidth and CPU, two things in short supply in a tiny embedded device. RSA would probably be a poor choice; Elliptic Curve Cryptography (ECC) exchanges fewer bits and generally computes faster than RSA. A paper comparing the two on an ATmega128 is available here; their bottom line is ECC secp160r1 can be computed in 0.82 seconds requiring 4k of memory, while their 1024-bit RSA implementation took 11 seconds and 7.4k.
But public key crypto is not normally used for the byte-by-byte communication; it's generally only used for key exchange for a symmetric encryption algorithm. Ordinary communications are protected using a self-synchronizing stream cypher. These cyphers resynchronize themselves in case of a transmission error or data corruption without needing another expensive key exchange.
Given what you've described, it sounds like you'll only have pairs of devices, or possibly a peer-to-peer network instead of a server-client environment; there may possibly be a 'master' device available. Are you planning on a 'pairing' step to introduce devices to each other in a trusted environment? Do they have to pair to the master device, or can they pair with a neighbor dynamically? Do your users have a setup step for each device? Is there an interface where the end users can inject each device with a secret key? Are you customizing chips for each customer? Or is every chip identical, with no differences between any of them?
If these are to be deployed generically to all your customers, they need to be secure against tampering. You don't want an attacker just reading the memory out of your chips with a JTAG reader. Even so, there's probably little hope of truly securing the communications, as reverse engineering chips and protocols is a hobby for many people. This would limit the amount of trust any device should place in the communications, meaning "don't use these devices to secure your building door locks, piles of money, trade secrets, burglar alarms, or other valuables." This may indicate that simple, light-weight obscurity might be enough -- it may not be worth investing in securing the communications given a motivated attacker.
But let's assume for the moment that you have some kind of key injection step that customizes chips for each customer. In that case, a pre-shared key might be a good way to go, where the same key is injected into each device, either during manufacture or at the customer's site. This eliminates the need for a key exchange during communications. You simply use the PSK to encrypt the data as it leaves, and decrypt the data as it arrives, using the self-synchronizing stream cypher. Also, consider the case where the customer wants to change keys - maybe someone stole one of their devices and they consider the key compromised. Customer site injection is a lot cheaper than sending the chips back to you.
If there's some kind of pairing step available between devices, where you introduce them to each other in a trusted environment, you can use this introduction period to exchange keys. Each network would have a base key, and each chip could get a copy. Typically this is done with a hardware-activated switch to prevent a rogue network injection of a key exchange request. If an attacker wants to break in, they have to be physically operating the device.
For higher security there's a protocol called DUKPT that is designed for protecting financial transactions. Each device is injected with a unique key derived from the base key, and a unique key is derived for each message sent. No end device ever receives the base key, so compromising one device does not compromise the network. As this was developed for cheap terminals in the 1990s, the CPU and message overhead is fairly small, making it good for embedded devices. But all communications have to originate at the client devices, and be forwarded to a decrypting server; there is no provision to communicate securely from peer-to-peer, and the key exchange is unidirectional from the client to the server.
Keep in mind there's usually nothing technically stopping an attacker from 'acquiring' one of customer A's devices after it has a key -- theft, maintenance, or even shipping errors can leave the devices to turn up on eBay some day. The attacker could then use his unauthorized device to communicate with the authorized device. This is a reason you'd need to be able to exclude a device or reset the network's base key.