FIXED: I'm going to put it up here, because people keep don't seem to read all the way down and keep telling me this is an exact duplicate of another thread while the solution proposed there (using edge split or auto-smooth) did not fix my issues. In the end I reconstructed the model using the shrinkwrap modifier to cut holes and then manually merge and readjust the vertices of the outside hole for perfect smoothing. Thanks @Cegaton for the video that featured the shrinkwrap modifier.
Images of the reconstruction:
After two Boolean difference operations the model's geometry looked like this:
I guess it won't be a surprise that it resulted in this kind of crappy shading:
I know it's because of the ngons, but I don't know how to best fix or prevent matters. I've tried by making the geometry more complex, by subdividing existing edges and faces, and I've tried by making the geometry simpler, by snapping and joining dead-end vertices onto other ones, while respecting the shape of the model and keeping faces planar. Both these methods still left me with bad shading. I also tried doing the boolean operation with simpler objects, with fewer subdivisions, but that gave me similar issues. Or is my whole approach wrong-headed from the start and I need to go about creating the shape in another way?
PS: the issue is not fixed by using edge split modifier, to be clear.