i18n
Always use i18n functions (like _e() and __()), even if you don't know more languages, so others can do the l10n job for you.

Templates
At least, a template for archives, author, links, search and 404 must be provided.

Alternate CSS file
In your header.php link your style.css and a alternate-style.css in order to allow users to add personal CSS code without fear to loose it in the next theme upgrade.

Supported plugins
Add support to 3rd parties plugins is good. But always check if they exists using function_exists() function to avoid PHP errors.

Time and Date format
Don't use your own time/date format with the_date() and the_time() functions. Use get_option() function, like the_date(get_option('date_format')) and the_time(get_option('time_format')) instead. And remenber, if you call the_date() function twice or more in one page, only the first will echo the date. the_time() function don't have this behavior.

Lightweight
Use WordPress own resources if is possible: i.e. don't add jquery.js, use wp_enqueue_script() function, like wp_enqueue_script('jquery'), and so on...

Widgets
Even if widgets are not your thing (like me), make your theme widget-ready. It's so easy, and sooner or later someone will ask you to do it.