Problems designing high pass FIR filter with $f_\textrm{cutoff} \ll f_\textrm{s}$
@poipoikuroi: I don't think you are "overlooking" anything. If IIR filters are allowed you can build a simple "DC Blocking" filter with a narrow stopband (using floating-point arithmetic) centered at zero Hz.  (Search the web for DC Blocker.) However, those filters have wildly nonlinear phase near zero Hz. 

If linear phase is mandatory then your super-narrow stopband width requirement makes your FIR filter impractical due to needing thousands of taps.  So as you've noticed, you'll have to either widen your stopband width or lower your data sample rate. I developed a computationally-efficient linear-phase DC blocking filter that uses cascaded moving average filters. Perhaps it might be of interest to you. See:
https://www.dsprelated.com/showarticle/58.php

Does your eeg software package use one or two FIR filters to remove both DC and line noise? If your eeg software uses a single high-pass FIR to remove both DC and line noise, then I'll bet that filter's stopband width is, say, 90 or 100 Hz. (Which is much more "practical" than the FIR filter you're trying to design.)