I would suggest one of the new sub notebooks that comes with Linux pre-installed. The ultra mobility would make for a better companion to your MacBook than having another full sized notebook. And, as an added bonus, you don't have to worry about driver support.

Personally, I've been pretty pleased with my OLPC XO, but that's mostly because I use it as an ebook reader all the time. If I just wanted a laptop, then I would have gone with the EeePC.