GPS doesn't work offline on Samsung Galaxy S4
If your GPS is set to use AGPS mode, it doesn't work at all when offline for some reason.

Go to Settings - General - Location - Mode - GPS only. I didn't notice at first that it was a selectable option.