List authors of site with link and gravatar

To answer your problems:

Sorting by post count

You can collect all the information you need in to an array and sort that array by number of posts , like this:

    //function to sort array by filed
    function authors_orderBy($data, $field){
       $code = "if (\$a['$field'] == \$b['$field']) {return 0;} return (\$a['$field'] < \$b['$field']) ? 1 : -1;";
       usort($data, create_function('$a,$b', $code));
       return $data;
    }

then change your code a bit like so:

        $blogusers = get_users_of_blog();
        if ($blogusers) {
            $au = array();
            foreach ($blogusers as $bloguser) {
               $user = get_userdata($bloguser->user_id);
               $post_count = count_user_posts($user->ID);
               $au[] = array('user_id' => $user->ID , 'nicename' => $user->user_nicename, 'display_name' => $user->display_name, 'email' => $user->user_email ,'post_count' => $post_count);
            }

            //Sort array
            $au = authors_orderBy($au, 'post_count');

           //then loop through the authors
           foreach ($au as $aut){
             if ($aut['post_count'] > 0) {
                echo '<li>';
                echo '<a href="'.get_bloginfo('url').'/author/' . $aut['nicename'] . '">'.get_avatar($aut['email'], '36').'</a>';
                echo '<a href="'.get_bloginfo('url').'/author/' . $aut['nicename'] . '">'.$aut['display_name'] .' ('.$aut['post_count'].')</a><li>';
             }
           }
        }

get_users_of_blog is a depreciated

It’s weird because looking at the codex Yes this function is depreciated and you should use get_users() which should be shipped with Version 3.1

     /**
     * Retrieve list of users matching criteria.
     *
     * @since 3.1.0
     * @uses $wpdb
     * @uses WP_User_Query See for default arguments and information.
     *
     * @param array $args
     * @return array List of users.
     */
    function get_users( $args ) {

            $args = wp_parse_args( $args );
            $args['count_total'] = false;

            $user_search = new WP_User_Query($args);

            return (array) $user_search->get_results();
    }

but if you look at wp_list_authors it uses get_users_of_blog() be itself.

Hope this helps.