Embedded boundary methods (EBMs) for Computational Fluid Dynamics (CFD) and nonlinear fluid-structure interaction (FSI) - also known as immersed boundary methods, Cartesian methods, or fictitious domain methods - are the most robust methods for the solution of flow problems past obstacles that undergo large relative motions, significant deformations, large shape modifications, and/or surface topology changes. They can also introduce a high degree of automation in the task of grid generation and significant flexibility in the gridding of complex geometries. However, just like in the case of their counterpart body-fitted methods, their application to parametric flow computations at high Reynolds numbers remains today impractical in most engineering environments. For body-fitted CFD, the state of the art of projection-based model order reduction (PMOR) has significantly advanced during the last decade and demonstrated a remarkable success at reducing the dimensionality and wall-clock time of high Reynolds number models, while maintaining a desirable level of accuracy. For non-body-fitted CFD however, PMOR is still in its infancy, primarily because EBMs dynamically partition the computational fluid domain into real and ghost subdomains, which complicates the collection of solution snapshots and their compression into a reduced-order basis. In an attempt to fill this gap, this paper presents a robust computational framework for PMOR in the context of high Reynolds number flows and in the EBM setting of CFD/FSI (PMOREBM). The framework incorporates a hyperreduction approach based on the energy-conserving sampling and weighting (ECSW) method to accelerate the evaluation of the repeated projections arising in nonlinear implicit computations; and a piecewise-affine approach for constructing a nonlinear low-dimensional approximation of the solution to mitigate the Kolmogorov n-width barrier to the reducibility of transport models. The paper also assesses the performance of the proposed computational framework PMOR-EBM for two unsteady turbulent flow problems whose predictions necessitate or benefit from the application of an EBM; and two shape- parametric steady-state studies of the academic type but of relevance to design analysis and optimization.