Bevel an inset face with resulting clean edges
Here's a somewhat shorter solution, but it still requires a bunch of work.
Create the bevel:

Use the knife tool to replace the missing edges:

Select and delete the edges you don't want, using dissolve edges:

and there you go:

This leaves you with all quads in the replaced area, but a concave quad can be just as bad as an n-gon.