What should I do to make generated avatars different for anonymous comments?

There are two ways to customize the default avatar:

1. Add a new default avatar to Settings/Discussion.
2. Change the output of get_avatar().

Let’s start with the first option; this processes slightly faster.

Add a new default avatar to Settings/Discussion

There is a filter 'avatar_defaults'. You can add more avatars here.
You get an array of default images where the key is an URL and the value the visible name.

Sample Code

add_filter( 'avatar_defaults', 'wpse_58373_kitten_avatar' );

/**
 * Add a new default avatar.
 *
 * @param  array $avatar_defaults Key = URL, Value = Visible name.
 * @return array
 */
function wpse_58373_kitten_avatar( $avatar_defaults )
{
    $avatar_defaults['http://placekitten.com/32/32'] = 'Kitty';

    return $avatar_defaults;
}

Result

Change the output of get_avatar().

get_avatar() searches in an option named 'avatar_default' first. We can hook into 'pre_option_avatar_default' and return a custom (random) URL.

Sample code

add_filter( 'pre_option_avatar_default', 'wpse_58373_custom_default_avatar');

/**
 * Return a random image URL
 */
function wpse_58373_custom_default_avatar()
{
    /* We use images from WP here, you should change this and put some default
     * images into your theme or plugin directory.
     */
    $base_url = admin_url( 'images' ) . "https://wordpress.stackexchange.com/";
    $images   = array ( 'wp-logo-vs.png', 'wpspin_dark.gif', 'yes.png' );
    $rand     = rand( 0, ( count( $images ) - 1 ) );

    return $base_url . $images[ $rand ];
}

Result

As you can see – you should return an image with a size that matches your theme’s avatar size. 🙂