This is a bit of an unconventional approach, but here's my plan for when I buy a Macbook Air over the summer:
* Keep OS X / X11
* Install a command line Ubuntu VM in Parallels
* Set up the VM as an SSH server and configure public/private key authentication
* Configure any necessary filesystem sharing in Parallels
* Configure OS X to run your Ubuntu VM on startup in headless mode (background / non-graphical)
* Replace your OS X bashrc with 'ssh -Y localhost'; this will cause any terminal you open to run a Linux shell, with the capability to open graphical applications (I'll personally be using TotalTerminal; I'm a sucker for Quake-style terminals)
In the end, you pretty much have the best of both worlds. You get an Apple-polished day-to-day experience (with no hacking required for things like multitouch gestures), with all the power of Linux also at your fingertips.
---
Though, if that doesn't sound like your thing (or you just really want to be rid of OS X), my original plan before I had that idea was just to go with my standard Kubuntu. Kubuntu is an incredibly polished KDE distro in my opinion (despite its naysayers), and from what I can tell KDE is the only desktop environment which really rivals OS X (except maybe Unity, which I haven't played much with). Given the latest release, now is a better time than ever to get rolling with a *buntu.
Also, no matter which distro you choose, if you're using an Air it seems you'll need this: http://code.google.com/p/touchegg/