How do I make my service dependent on another module existing?
Yep, you need a ServiceProvider that only registers the service if the module exists in the container.modules parameter

See https://github.com/md-systems/file_entity/blob/8.x-2.x/src/FileEntityServiceProvider.php#L25 for an example