We present non-normal linear stability of embedded boundary (EB) methods employing pseudospectra and resolvent norms. We analyze the stability of the linear wave equation in a domain with an embedded boundary in one and two dimensions. In particular, we characterize the stability in terms of the normalized distance of the EB to the nearest ghost node (α). An important objective is that the CFL condition remains unaffected by the EB which is taken to be that of the underlying grid (as if the EB is absent or aligned with the regular grid). We consider various spatial and temporal discretization methods including both central and upwind-biased schemes. Stability is guaranteed when where ranges between 0.5 and 0.77 depending on the discretization scheme. The stability analysis is also briefly examined for the one-dimensional advection-diffusion equation. Sharper limits on the sufficient conditions for stability are obtained based on the pseudospectral radius (the Kreiss constant) than the restrictive limits based on the usual singular value decomposition analysis. A resulting sufficient condition for stability is that the intersection of the EB with the surface normal passing through a ghost node () must lie within the ghost cell ( distance from ). This condition leads us to propose a simple and robust reclassification scheme for the ghost cells (dubbed “hybrid ghost cells”) to ensure Lax stability of the discrete system. This has been tested successfully for both low and high order discretization schemes with transient growth of at most . Moreover, we present a fourth order EB reconstruction scheme taking into account both accuracy and stability.