It's not a shading problem, you have inner faces, as soon as you give your object a Subdivision Surface modifier it makes them surface through the outer faces, so the best is probably to remove them:
In edit modeMessage to Gorgious: Select > Select All by Trait > Interior Faces then Mesh > Delete > Faces. won't work in that cases as these inner faces are connected to the outer ;)