Foreach inside foreach

First, I’d extract all the slugs of the recommended colour terms with something like this:

$recommended_colours = wp_get_post_terms($post->ID, 'recommended_colours');
$recommended_colour_slugs = array_map(function($colour) {
    return $colour->slug;
}, $recommended_colours);

… which leaves you with a $recommended_colour_slugs array that looks like this ['blue', 'green'].

Then you can loop over your colour terms and use an if-else to check whether the current colour exists in the $recommended_colour_slugs array and set the css class for that item accordingly.

$colours = wp_get_post_terms($post->ID, 'colours');

foreach($colours as $colour) :
    $colour_class = $colour->slug;
    $colour_title = $colour->name;
    if (in_array($colour->slug, $recommended_colour_slugs)) {
        $colour_class .= ' recommended';
    }
    ?>
    <div class="<?php echo $colour_class; ?>" title="<?php echo $colour_title;?>"></div>
<?php endforeach;