I was looking at info on my Teensy++ and found that it can use 64k bytes of directly addressable external ram. It's an AT90USB1286. I am finding other AT90 chips able to use external ram and I see that the Arduino MEGA can also use external ram, Rugged Circuits has memory shields for them. Chances are that the 1284 can use it too.
Yes you should count bytes and be aware as you write your code. Even on a full PC. Fat code is why we need desktop supercomputers to run apps way slower than they should. On an MCU it's critical. Do you watch how high you hold your head in low places?