I guess most people still use Outlook Express for E-mail as it comes with IE and handles basic tasks well enough. We already covered most customizable parts of it. They aren't many but you can modify the files a bit to change the folders and toolbar icons, more info on the modifications list. Throbber can also be modded as well as the window title, check here.

Other email clients (mostly shareware):

• Eudora (free light version, all) is considered the best, lots of features, nice interface, plug-ins, good HTML support.
• Pegasus Mail (free, all) is also a good freeware alternative. Features: filtering and mailing list support, nice interface, support for the latest mail standards, animated traybar icon.
• the BAT (shareware, all) has a good feature-set (Mail Ticker...), is easy to use, but lacks a few advanced features (HTML support...).
• Poco Mail (shareware, all) also has good features, and has an nice interface with customization options (for the buttons, etc...), but lacks some advanced options.
• PMMail (shareware, 9x/NTx). Good filtering technology, easy to use interface, advanced configuration options, but medium HTML formatting and no IMAP support.
• Mail Control is good but lacks some options.
• Kaufman Mail Warrior (shareware, all) also has good features (multiple accounts...).
• iScribe (free, all), is light but featured, looks nice.
• NeoMail (free) is a web-based e-mail client that can be installed on any UNIX mail server that is also running a web server. Development is temporary cancelled though.
• Incredimail (shareware, unlimited trial) is a skinnable mail client. You can also send multimedia messages and have the program autocheck for messages with a custom notifier.
• NeoPlanet also has a mail client, rather rudimentary but skinnable, more info here.
• CutTheRedWire pointed out JBMail (free for one account), a very simple E-mail client, great for on the go and to delete mail without having to download it first.

Some apps that check your mail for you:

• EzPop (free, Win 9x/NT/2k), will check every x minutes if you have mail, and will warn you by a mailbox image, a sound or a pop-up. From Thibaud Dijan, creator of HoverDesk, it's pretty cool, of course skinnable and new version is up!
• BoxIP (shareware, all) does the same, with a little more options.
• 3D Mail Effects (shareware, all) is another one.
• And also free, but discontinued, DeskPop.

Wanting to save your old Outlook Mail? kendo pointed out DBXtract (free, all) that extracts all mail and news messages into individual dbx files in a folder.

AIM (free with ads, all) is a major player with quite a lot users (every AOL member for a start). Easy to use (like most of them) it also includes news tickers, has file transfer ability, can check your email, allows to have real live (voice) conversations (AIM Talk) and to create chat rooms. It cannot send messages to offline buddies. Also, you can replace the default sounds by your own. Note that AOL decided to let access to their network only from their own software... but that didn't seem to work out well (protections bypassed by most clients).

For the looks, buddy icon can be changed by anything you'd like, but for more in-depth customizing Resource Hacker is required, more info about modifying files here. About everything (Bitmaps, menus...) is contained in Aimres.dll, as well as the URL of the buddy icon selection window (at String #65, line #1037, replace the url (depends on language) by the location of your own html file). AIM Icons net has a (nice) collection of tips and tricks you'd want to use and some more...

You may also use AIMazing, it will replace the banners with a visualization plug-in for Winamp.

For versions 4 and higher, Observers gives a procedure on how to remove the ads and DeadAIM or AIM Ad Remover should automate that. Furthermore, CutTheRedWire pointed out MyIM, a free plugin removing the adds but also allowing to customize and improve AIM (updated often).
To change the maximum buddy number edit the key in the registry.

Icq (free with ads, all) is pretty popular out there, huge community. Can send messages to offline buddies (it's almost the only one that does that), create instant chat rooms, has file transfer ability, etc...

It has it's own skinnable extension called Icq plus (free, all). When installed, ICQ Plus integrates with ICQ by adding a menu item to the main menu allowing you to change its appearance, not free-form but sufficient.Alexandrie is quite known for her skins!

ICQ Color Picker allows you to easily pick any RGB true color for ICQ's Send Message Dialog's Text Box, whereas ICQ would only let you choose from the 16 basic colors.

Miranda ICQ is an alternative. Lots of plugins available, and can handle MSN too.

IRC (Internet Relay Chat) consists of various separate networks (or "nets") of IRC servers, machines that allow users to connect to IRC to chat on channels or directly. Feature-wise you can transfer files and the clients are often scriptable, allowing lots more actions. More info at IRChelp.

There's lots of IRC clients, most known is probaly Mirc (register, all), not quite skinnable, but you can change all the colors and has good scripting.
Bersirc (free, all) is also good, using scrow's icons, lots of features, advanced scripting, plugins etc... Xchat (free, 9x/NT/more?), as craeonics says "looks pretty weird, but that's because it's a *nix port".

Less advanced are pIRC (free, 9x/NT), orbitIRC (shareware, 9x/NT), vIRC (beta...) and xircon (free, all, no more in development).

Microsoft throws once again it's own app in the business (available by default in XP... sounds familiar ?), MSN Messenger (free but with ads, all) is an AIM competitor. The interface is intuitive (as with all of them), it can make phone calls and send files but it won't send messages to offline buddies (unlike ICQ) and is limited when it comes to organizing buddies.

You can remove the banners as well as hack the default banner and icons; mongoose found a way to remove the banners:

Close messenger and clear the contents of links.txt (in program directory), then set it to read only. Restart messenger and you're done.

Change the backdrop of the window by changing lvback.gif and by using a resource editor on the programs executable you can change the default banner and icons. In the end you could have something similar to his screenshot. Here's some details on bitmaps/icons mongoose found in the executable:

Bitmaps Gifs Not using MSN and find its integration in Windows XP annoying ? MS made it very hard to stop from running at startup using the regular channels (msconfig). But go to your \Windows\Inf\ folder (hidden) and find sysoc.inf, open in notepad. There's a line there. Take "hide" out, but leave the comma (msmsgs=msgrocm.dll,OcEntry,msmsgs.inf,,7). Close and save, then go to the Add and remove programs applet in the control panel and you will be able to uninstall windows messenger (Windows components item).

Yahoo messenger (free, all) is good too: has ability to save and print your conversations, to create a chat room automatically, to send messages to friends even if they're not online when you are (like ICQ). The latest version adds Webcam capabilities.

It wasn't very skinnable a the beginning, but now is okay. Toolbars, Status icons and Background can be easily changed (comes in themes, find them from here). For total control the use of a window changer is required, detailed here. More could be done also by modifying its files...
You can create new (or customize your own) status messages and their icons by modifying the "HKCU\Software\Yahoo\Pager\profiles\UserID\Custom Msgs" key in the registry.

Jabber (free, 9x/NTx) is another IM network, open source and XML-Based (so very customizable) but not very popular (yet?).

There are some of these that do a cool job, combining several apps, (sometimes except AIM, because AOL tries/tried to forbids to access their network except from their own software...).

Trillian (free, all, pro version available), most popular, handles all the chat format talked here and is skinnable. Skins are not easy made though, and skin format is evolving, so not many skins are available. Unfortunately you can't register new accounts (yet), and the app sometimes has limited functionalities because it has to catch up on the newest features. Miranda IM is also great. It's designed to be resource efficient and plugin based, so you only run what you need. It's also open source and skinnable, definitively a good trillian contestant.

Indiatimes messenger supports ICQ, MSN, AIM (?) and Yahoo, you must have an indiatimes.com email account to use this service, and it is not skinnable.

Odigo (free, all) is another one, skinnable, doing ICQ, Yahoo and MSN, smaller look with no individual windows, but not very stable nor very supported for the moment I think.