Accessibility сервис работает в фоне, в другом потоке, но в каком потоке будет работать обычная служба запущенная из него, такой вот вопрос
Не имеет никакого значения как и откуда вызван запуск службы - она будет работать так, как должна.
Это отдельный компонент приложения со своим жизненным циклом, а жизненный цикл всегда обрабатывается в главном потоке.
То есть базовые методы-колбеки службы, такие как onStartCommand(), onCreate(), onBind(), onDestroy() и т.д. будут вызываться в главном потоке. Дополнительные API в классах-потомках будут работать согласно их документации.
И не надо путать фоновый поток и фоновый режим - это "две большие разницы".
Фоновый режим - это когда служба работает скрытно от пользователя, "на фоне" открытой активности, система считает такую службу не важной и после закрытия всех активностей приложения её уничтожает. Все службы по умолчанию работают в фоновом режиме, а чтобы перевести её в режим "переднего плана" нужно вызвать startForeground(), требующий уведомление.