A minimal surface in a random environment (MSRE) is a $d$-dimensional surface in $(d+n)$-dimensional space which minimizes the sum of its elastic energy and its environment potential energy, subject to prescribed boundary values. Apart from their intrinsic interest, such surfaces are further motivated by connections with disordered spin systems and first-passage percolation models. In this work, we consider the case of strongly correlated environments, realized by the model of harmonic MSRE in a fractional Brownian environment of Hurst parameter $H\in(0,1)$. This includes the case of Brownian environment ($H=1/2$ and $n=1$), which is commonly used to approximate the domain walls of the $(d+1)$-dimensional random-field Ising model. We prove that surfaces of dimension $d\in\{1,2,3\}$ delocalize with power-law fluctuations, and determine their precise transversal and minimal energy fluctuation exponents, as well as the stretched exponential exponents governing the tail decay of their distributions. These exponents are found to be the same in all codimensions $n$, depending only on $d$ and $H$. The transversal and minimal energy fluctuation exponents are specified by two scaling relations. We further show that surfaces of dimension $d=4$ delocalize with sub-power-law fluctuations, with their height and minimal energy fluctuations tied by a scaling relation. Lastly, we prove that surfaces of dimensions $d\ge 5$ localize. These results put several predictions from the physics literature on mathematically rigorous ground.