Классы и методы в разных пакетах, должны быть PUBLIC?

Может что-то и не понимаете. В частности разницу между интерфейсом класса и его внутренней кухней. С public методами вы разобрались видимо. Проблема в том как они реализованы. Если они состоят из простынь кода - возможно есть необходимость свернуть простыни в private-методы. Если по вашей логике класс клиент для одной задачи вынужден последовательно вызвать 3 public метода одного класса в стороннем package - эти 3 класса надо сделать private и сделать 1 public метод, внутри которого последовательно вызываются эти 3 private. В любом случае без вашего кода я тут могу долго фантазировать о том что вы там понаписали и почему у вас все public.

Судя по всему вы построили слишком сильно-связанный код. При разнесении в разные пакеты вы столкнулись с ситуацией, что всякий класс взаимодействует со всяким другим классом и соответственно всё должно быть Public. Правильным решением в таком случае является уменьшение связанности кода, например, с помощью паттерна ООП фасад. То есть, для уменьшения связанности кода вам необходимо разбить код на группы по функциональности и через фасад предоставлять необходимую функциональность одной группе другой группе.
К примеру, вы можете создать группу классов работы с сетью, группы разных видов бизнес-логики, группу классов графического интерфейса.
Фактически, вы будете проводить декомпозицию монолитного куска кода на кластеры по некоторой логике. Это задача довольно нетривиальна, однако она как раз позволит верно инкапсулировать логику в пакеты и создать к ним адекватные интерфейсы с помощью фасадов. В результате вы сможете скрыть сложность внутренней логики за фасадами и даже впоследствии вынести некоторые классы в библиотеки.