This research investigates suitable bio-carriers for the anaerobic ammonium oxidation (anammox) process. This study evaluates the efficiency of the anammox process by assessing nitrogen removal efficiency using five different bio-carriers: fine and coarse polyurethane (PU) sponges, a melamine sponge, Scotch Brite, and a loofah. Among the tested carriers, the reactor of the fine PU sponge media exhibited the highest nitrogen removal efficiency, achieving an 87% removal rate. This high efficiency was attributed to the substantial biomass containment, evidenced by a measured mixed liquor volatile suspended solids (MLVSS) amount of 1414 mg/L. Subsequently, the fine PU sponge, exhibiting the highest efficiency, was selected for further modification with a polyvinyl alcohol–sodium alginate (PVA-SA) gel coating to study the impact of methanol inhibition on nitrogen removal efficiency. An optimal modification condition was determined, utilizing concentrations of 8% PVA and 1.8% SA for the fine PU sponge media. The modified PU reactor exhibited the highest resistance to methanol inhibition, followed by the attached growth fine PU sponge reactor and suspended growth reactor. These findings suggest that there are benefits to using modified PU media for the anammox process in the field.