Extract your encapsulated logic into smaller classes. Keep doing this until you get classes that adhere to the SRP principle and have one, and only one responsibility. Write tests on those classes to test that they perform the little responsibility that they have correctly. Compose your bigger classes from these small classes, until you have the one
ComplexProjectFacade which is composed from smaller classes, and so on.
By doing this, you create small, focused and easy-to-understand classes. The fact that they have methods that are public and can therefore be tested is a happy side effect from the fact that you now have code that is easy to understand. Whenever I hear somebody argue about having to make classes or methods public purely for the sake of testing, I try to make them realize that they are also more clearly adhering to principles that lead to better code (e.g. SOLID).
How you do beyond this is more up to personal preference:
- Putting the tests next to the code in the same assembly pollutes your released code with the tests. They will be in the same DLL which increases size, and so on. You probably do not want to release your compiled test code with your application but if you have no qualms with that, it's a valid approach. Still requires you to have every class marked as Internal
- Keeping the classes public means that the exposed interface of your DLL becomes more complex. Users wanting to use your DLL will see a wide range of classes and it might not be immediately obvious what class to use to perform something. Proper usage of namespaces might prevent this somewhat as you can limit the root namespace to the facade and putting all the other classes into separate (sub-)namespaces, making it more obvious what your users need to look at.
- InternalsVisibleTo allows you to keep all your small classes internal to the assembly, limiting the exposed interface of your DLL to things you really intended to have exposed, but requires you to keep all the classes internal and limits you to having to recompile your library with a new InternalsVisibleTo-attribute if you want to add a new test assembly.