Where (or when) should I register a new taxonomy?

Using activation_hook isn’t the best idea. Here’s why (let’s take a look what Codex says about activation hooks):

When a plugin is activated, the action ‘activate_PLUGINNAME’ hook is
called. In the name of this hook, PLUGINNAME is replaced with the name
of the plugin, including the optional subdirectory. For example, when
the plugin is located in wp-content/plugin/sampleplugin/sample.php,
then the name of this hook will become
‘activate_sampleplugin/sample.php’. When the plugin consists of only
one file and is (as by default) located at
wp-content/plugin/sample.php the name of this hook will be
‘activate_sample.php’.

You can read more on the full process flow here: https://codex.wordpress.org/Function_Reference/register_activation_hook#Process_Flow

It means, that activation hook is run only once – when the plugin is activated, ergo, during every other request, when the plugin is already active, your taxonomy won’t get registered, so WordPress won’t see/understand it.

And of course you register your taxonomy so it is available during every request, when plugin is active.

So yes – using init action is much better idea… And Codex is clearly suggesting that:

Use the init action to call this function. Calling it outside of an
action can lead to troubles. See #15568 for details.