This dissertation details two studies at the intersection of microhydrodynamics and biophysics: the motion of (i) a straight-swimming flagellated bacterium (e.g., Escherichiacoli) and (ii) a model (spheroidal) active particle (squirmer), in a complex biological fluid (e.g., mucus). Biological fluids are typically concentrated polymer solutions or gels, possessing three primary features, viz-a-viz, non-Newtonian rheology, yield stress, and microstructure. Understanding how bacteria and active colloidal particles navigate such complex environments is therefore critical for several biomedical and engineering applications, such as advancing strategies to combat infectious disease, guiding the design of bio-mimetic microswimmers for targeted drug delivery and invasive surgeries, and designing synthetic active materials with tunable properties. Although several earlier studies have addressed this topic using computational and theoretical models, they do not consider the combined nonlinear effects of the three aforementioned features of the complex fluids on the swimming microorganism. This work addresses this gap, and its primary contributions include: i) development of a novel two-fluid mathematical model for complex fluid media that accounts for the effect of microstructure leading to differential response of the biofluid components at a length scale comparable to the microstructure length scale, ii) development of a high-fidelity computational framework using a novel physics-informed numerical algorithm to solve the associated governing equations with accuracy and efficiency, iii) an analysis of the individual and combined effects of microstructure, non-Newtonian rheology and yield stress of the complex fluid on the motion of a swimming bacterium and a squirmer, which, in some cases, predicts an enhancement in their swimming speed relative to the speed in a Newtonian medium.