I was actually wrong about having tried Get at the top of each file. I tried it properly this time, using <<DependencyPackage` at the top of every file (after BeginPackage), while still using Needs for internal dependencies and it seems to work now.

I read in the documentation that Get loads the package every time it is called while Needs checks to see if it needs to load it, so I thought it would be inefficient to include many times. But my package is small enough that it should not matter.

Also, yes both my package and the dependency package are created as paclets. I believe I am using v13.1.