Starter Themes for Drupal 6

Well, I have extensive experience and am probably one of the more able to give an answer to this, since I built two of the more popular Starter themes - Adaptivetheme and Genesis.

You ask the 64000 dollar question, and its really hard to answer. It all comes down to two things in my mind:

1 - Use case
2 - Personal preference

Most of the popular starter themes are very well coded and will do the job, they just all do it slightly differently.

Adaptivetheme and Fusion are conceptually similar - they both have many theme settings and are very flexible. The concept is to remove the hurdle of *layout* (the theme takes care of that by itself via theme settings and other trickery such as the Skinr module, Panels Plugins and Gpanels). Under the hood these themes take very different approaches so the PHP is just worlds apart. Fusion adds DIV wrappers and many CSS classes for each page element - this results in lots of design redundancy - if you want that, use Fusion. Adaptivetheme on the other hand is about minimal code (small footprint) and instead provides very clean tpl files for you to add extra HTML if you need it and many theme settings for adding extra CSS classes. In short Fusion is top down, Adaptivetheme is bottom up.

Zen and Genesis are quite similar - this is no accident. I started off using Zen but I ended up modding it so much I decided to simply build my own base theme. Where they differ is in code semantics and the structure of the theme files. Genesis is easier to get started with than Zen (the subtheme just works strait away), however there is a module that can generate a Zen subtheme which makes this task a breeze.
Genesis has better semantics and to be frank I have never liked Zens content source order. Don't get me wrong, Zen is a fantastic theme and has provided some of most exciting features and advanced solutions to some very difficult theming problems in Drupal - the PHP is superb. Genesis has far more layout tools than Zen - its much easier to build complex layouts with using the body ID tag concept and Gpanels.

Theres a bunch of other more simple starter themes, and they are worth looking at - Clean, Basic and Foundation are all worth trying - you may really like their approach.

There are also many grids based themes (Fusion and Adaptivetheme also make use of grids, Fusion more so and is really a full blown grids theme). There is Blueprint, NineSixty and even Zen960.

BTW, if you are building a Dark theme, then Genesis has a dark subtheme and Adaptivetheme has a dark stylesheet you can enable for instant support for dark themes (this is not trivial to achieve in Drupal and will save you a lot of time).

So - thats a very brief rundown, and in no way scratches the surface of what each of these themes is capable of. If its your first real crack at Drupal theming then you cant really go wrong which ever theme you choose. If it were me, well I would use Adaptivetheme (the DEV version for sure...) because it totally kicks ass. Whatever theme you choose, give it some time to sink in, get to know it, they can all do what you want;)