Can you have a single set of “canonical” categories shared by all blogs?

A more elegant solution would be to create a MU (must use) plug-in and drop it on the network. This plug-in would check (per-site) if the categories exist and, if not, add them as appropriate.

Here’s some untested example code:

<?php
$default_categories = array(
    'my_first_cat',
    'my_second_cat',
    'my_third_cat'
);

foreach($default_categories as $cat) {
    if( get_cat_ID( $cat ) != 0 ) continue;

    wp_insert_term( $cat, 'category' );
}

This should loop through your list of categories and attempt to fetch the ID of each. If the category doesn’t exist, get_cat_ID() will return “0” so you know to insert the category. This code won’t set the slug, description, parent, etc … I leave that as an exercise for you to complete.