Gmail, my absolute favorite mail anything client ever, just rolled out themes! I can't decide between Terminal, which makes me feel like a hacker, and Ninja, which is, well, Ninja!
As you might expect from a Google product, the themes are all readable, easy to change, and don't affect the functionality of Gmail one bit. Also, if you're not as cool as a hacker or a ninja, there are several hip-but-subdued palettes for your mailin' pleasure:
Bonus: some themes appear to be time-zone-aware, andchange based on your location and the time of day.