Disclaimer: I respect people of all distro beliefs, just looking for a hand finding my own.
Since Ubuntu seems to be devotedly jumping the Unity shark and has started releasing software a little closer to beta than I am comfortable with, I'm looking for a new daily-use distro. I have heard good things about Arch and Mint, but I am mostly looking for usable system which emphasizes stuff like having flash and wireless just work and has reasonably modern compiled versions of most packages (the reason debian has not been my default). Bonus if the community already tested this distro for MacBook Airs.
(Just running X11 on OSX Lion is not an acceptable solution for me, Lion broke a lot of my X11 stuff and it is very tedious to compile them anew for Lion)
* 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/