I'm taking some of the new Drupal 6 themes for a spin. Here's what I've added so far:

• Amadou: XHTML & CSS based multi-column theme with both side bars on the right. Note: not yet tested.
• Bluebreeze: A blue, tableless, fluid width theme. Note: not yet tested.
• Bluebreeze fixed: A fixed-width version of the bluebreeze theme. Not yet ported! Note: not yet tested.
• Deco: Modern, tableless, multi-column, fluid width theme with art deco looks. Note: Wow! This was developed at the Google Summer of Code, apparently. It's not really a general purpose theme though or necessarily a good starting point to build a new theme. But a nice out-of-box theme, for sure!
• Nista: Left or right sidebar, fixed width, clean. Note: not yet tested.
• Salamander: Multi-column, 1 color style, 12 fully collapsible regions, fixed or fluid width theme (default), easy configuration. Note: not yet tested.

Note that themes seen in the "Switchtheme block" to the right that are not in this list are part of the core (included) Drupal themes.