Getting rid of Gmail theme-backgrounds
I love that Gmail added theming functionality, but I would actually like some of the themes more without the backgrounds. This isn't a fancy solution, but it's more of a reference for myself. You could also use plugins that let you modify the CSS, but I'm just using Adblock-plus for Firefox here.
Take for instance the Pebbles theme:

Not my cup of tea, but I love those neutral colours.
The easiest thing to do is to add a Block-rule in Adblock-Plus:
1 2 | https://mail.google.com/mail/images/2/5/pebbles/rocks_tile.jpg */images/2/5/pebbles/rocks_tile.jpg /*wildcard version - for Google Apps*/ |

Refresh Gmail, and it's gone:

Other blockable backgrounds (some of the themes are day-of-the-week specific, so I'll add more to the list as I find them):
1 2 3 4 5 6 7 8 9 10 11 12 | *images/2/5/pebbles/rocks_tile.jpg *images/2/5/mountains/mon/* *images/2/5/mountains/tue/* *images/2/5/mountains/wed/* *images/2/5/mountains/thu/* *images/2/5/mountains/fri/* *images/2/5/mountains/sat/* *images/2/5/mountains/sun/* *images/2/5/tree/sunny/header_bg.jpg *images/2/5/ocean/weekdays/weekday_header.jpg *images/2/5/planets/base/star_tile.gif *images/2/5/planets/saturn/saturn.jpg |
Gmail cleans up navigation
Big thanks to Gmail for taking out the annoying 'sites' from the menu:

Awesome.
Gmail adds undo-send-email in labs
How many times have you sent an email message and immediately wished you didn't?
Gmail has added a feature that people have been requesting for ages. If you enable the feature (in labs), it adds a 5 second delay to your emails being sent. During the delay, you have the option to undo the email being sent (Awesomeness).

I have to wonder how long it's going to be before other webmail services copy this feature.
Gmail introduces custom themes (awesome)
Gmail has added the ability to edit your own custom theme-colours. Click on settings -> themes -> "Choose your own colors" which then opens a window where you can edit colours. The changes can be saved and seen immediately.

Example:

Gmail invites

This used to make sense when you couldn't get a Gmail account unless you got an invitation from someone who already had an account.
Now you can sign-up from the frontpage:

Now I have a (minimised) invitation box cluttering up my Gmail. I wish there was a setting to disable it (and I don't mean through a Greasemonkey script).
Gmail adds themes

The Gmail team have started rolling out theme-functionality. They haven't rolled it out to all users yet, but everyone should have it in a few days.
Go to 'Settings' -> 'Themes', and you'll be able to select a predefined theme.
If you're happy with the default theme - even that has been improved and tweaked slightly. You can also try out the old-school, terminal-style Gmail theme.
Sweet!
Thanks Gmail (for adding more rubbish emoticons)
First, we had these humble smileys:

Then gmail decided to give us a little more "eye-candy". This was really "cute".

I think the square-faces were actually implemented at the same time. Thanks for the variety!

Now we have these ones. Thanks again! I can express my individuality now!

Why? Enough already.