The purge command is a good start. In addition, you probably want to remove all the dependent libraries that were installed only to get Gnome. You can do that via autoremove in apt-get or, if you use aptitude, it should happen automatically.

Note that the purge command has an oddity: it purges items you remove explicitly, but only removes any automatically removed dependent packages. (That is, if you enter aptitude purge foo-bar and fizzbuzz gets automatically removed at the same time, foo-bar is purged but fizzbuzz is only removed.) So a good way to recursively purge is this:

aptitude purge foo-bar && aptitude purge ~c

The ~c search in aptitude finds any packages that were removed but not purged in the first removal.

One final note, if you haven't been using aptitude, always check its output the first time you try to run it. Don't simply say "Yes" to whatever it wants to do. Depending on what package manager you've been using, you may find that aptitude thinks some things should be autoremoved, but you prefer to keep them.

Based on ChrisiPK's suggestion to use Xfce, here are the detailed steps I took to rescue Ubuntu 11.10 Oneiric Ocelot from Unity.

For the looks:

1. Install Xubuntu-Desktop (for Xfce) by using sudo apt-get install xubuntu-desktop (If you want to undo this later, use this resource to get rid of the xubuntu packages).
2. Logout and using the settings "gear" icon, select Xfce session.
3. Upon logging in, you'll notice we're still a little ways away from an "Ubuntu Classic" appearance.
4. Start by making the lower panel full-width: Right click it and select Panel > Panel Preferences. On the display Tab, set the Size to something around 29, and the length to 100%.
5. I have the two panels organized as follows:

Panel 1 (top): Applications Menu - Places - Launcher (FireFox) - Separator (Set to Expand) - Notification Area - Clock - Session Menu - Action Buttons

--

Panel 2 (Bottom): Show Desktop - Window Buttons - Separator (Set to Expand) - Workspace Switcher

To remove the bubbles around desktop icons in Xfce

Edit (or create if it doesn't exist) ~/.gtkrc-2.0 -- Add to the file:

style "xfdesktop-icon-view" {
    XfdesktopIconView::label-alpha = 0

    base[NORMAL] = "#000000"
    base[SELECTED] = "#CFD784"
    base[ACTIVE] = "#FFE7BA"

    fg[NORMAL] = "#ffffff"
    fg[SELECTED] = "#ffffff"
    fg[ACTIVE] = "#ffffff"
}
widget_class "*XfdesktopIconView*" style "xfdesktop-icon-view"

The colors are hex, so adjust them according to the colors you would like to use (in fact, I personally only included fg[NORMAL] and commented out the rest (by using a # on each line).

For some functionality:

Now, I noticed several things were still missing, like the "Aero Snap" feature for windows, and the ability to arrange windows with Ctrl+Alt+numpad keys, and some other hotkeys were now broken (like Super+D (aka Windows key + D) to show desktop). To bring some of this back, I had to add Compiz back into the mix.

1. Under the Applications Menu > Settings > Settings Manager, go to Session and Startup. Under Application Autostart, add compiz --replace Log out and back in.
2. Install CompizConfig Settings Manager (CCSM): sudo apt-get install compizconfig-settings-manager.
3. Under Settings > CompizConfig Settings Manager, go to Key Bindings. Set Show Desktop to use Super+D to bring the show Desktop hotkey back.

For particular programs

NetBeans

You'll notice NetBeans looks ugly in Xfce (compared to Unity/Ubuntu). To fix that, add --laf com.sun.java.swing.plaf.gtk.GTKLookAndFeel to any and all launchers for NetBeans. For some reason, NetBeans on Unity loads the GTK Look and Feel, whereas under Xfce it loads a "Metal" Look and feel. Solution found here.

Last Words

I'm still hoping there is a more elegant way, and am still leaving this question open. Furthermore, my solution still has its oddities, and I am sure I am missing some features/functions -- I will try to add those as I come across them. Most notable at this point, is that the workspace preview icons are scaled incorrectly once you introduce Compiz to Xfce.

So instead of saving Ubuntu from Unity, this is actually going with Xubuntu instead, which means things like Firetray for Thunderbird have stopped working.