Your taxonomies register where you’ve told them to register, on the init hook which is the recommended hook for registering them. That much you are doing correctly.
And yes, the plugins themselves will load prior to that hook’s execution. You can see that by comparing the init hook’s location in the load sequence to the plugins_loaded hook’s placement.
You don’t say exactly what you are trying to accomplish but the trick is that any code intended to access your taxonomies needs to run on the init hook (possibly with a higher than normal priority) or on a later hook.