Trouble extruding complex shape from model
You need a quad strip running along where the two meshes meet to get your result without artifacts.

I would suggest:


Dublicate everything and hide the original versions of both objects.
Use a boolean operation to union the two copies.
In edit-mode, delete everything but the edge where they meet. You should now have a face less object that just describes the cut.
Bring back the originals and join everything.
Delete faces around the seam and create new faces that connects to the real seam.
Bevel the seam a slight amount.


Both objects:


Unioned objects with all but seam selected.


Original objects joined plus seam. Faces bordering seams deleted.


Merged geometry. Not all faces are quads, some are pentagons. Try to avoid that (I was in a hurry).


Geometry in wireframe view with beveled seam selected


Same geometry in solid view. It turned out ok.