  In this paper we study a version of (non-Markovian) first passage percolation
on graphs, where the transmission time between two connected vertices is
non-iid, but increases by a penalty factor polynomial in their expected
degrees. Based on the exponent of the penalty-polynomial, this makes it
increasingly harder to transmit to and from high-degree vertices. This choice
is motivated by awareness or time-limitations. For the iid part of the
transmission times we allow any nonnegative distribution with regularly varying
behaviour at $0$. For the underlying graph models we choose spatial random
graphs that have power-law degree distributions, so that the effect of the
penalisation becomes visible: (finite and infinite) Geometric Inhomogeneous
Random Graphs, and Scale-Free Percolation. In these spatial models, the
connection probability between two vertices depends on their spatial distance
and on their expected degrees. We prove that upon increasing the penalty
exponent, the transmission time between two far away vertices $x,y$ sweeps
through four universal phases even for a single underlying graph: explosive
(tight transmission times), polylogarithmic, polynomial but sublinear
($\Theta(|x-y|^{\eta_0})$ for an explicit $\eta_0<1$), and linear
($\Theta(|x-y|)$) in their Euclidean distance. Further, none of these phases
are restricted to phase boundaries, and those are non-trivial in the main model
parameters: the tail of the degree-distribution, a long-range parameter, and
the exponent of regular variation of the iid part of the transmission times. In
this paper we present proofs of lower bounds for the latter two phases and the
upper bound for the linear phase. These complement the matching upper bounds
for the polynomial regime in our companion paper.
