Extreme astrophysical environments, such as magnetars and core-collapse supernovae, are characterized by super-strong magnetic fields approaching 1018 G, which radically modify the quantum states of nuclear matter. In this study, we explore the structural response of astrophysically relevant finite nuclei to these intense fields, with a specific focus on critical waiting-point nuclei involved in r- and rp-process nucleosynthesis. Covariant Density Functional Theory (CDFT) is utilized to evaluate key bulk observables, including charge radii, deformations (β2), and total binding energies. To quantify model dependence and ensure theoretical reliability, self-consistent calculations are carried out using two independent parametrizations, the non-linear NL3* and the density-dependent DD-ME2 effective interactions, implemented within an axially symmetric, constrained relativistic mean-field framework. The explicit inclusion of the magnetic field breaks time-reversal symmetry and lifts Kramer's degeneracy, prompting a dramatic reorganization of the nuclear single-particle energy levels. Specifically, we identify critical level crossings at the Fermi surface that manifest at field strengths of B~1017-1018 G. This microscopic phenomenon triggers abrupt structural phase transitions, compelling transitional nuclei to shift from spherical configurations into oblate or prolate ground states. Additionally, we systematically study the evolution of the nucleon density distributions and the neutron–proton density difference as a function of the magnetic field. The systems exhibit a marked enhancement in total binding energy driven by the strong spin-alignment of nucleons. With both effective interactions yielding consistent structural and energetic shifts, we conclude that these magnetically induced modifications could significantly impact stellar weak interaction rates. Consequently, incorporating rigorous microscopic nuclear structure models is essential for the accurate simulation of nucleosynthetic pathways.