You really want colour for maps. I have been there (GPS on E-Ink). Try a Kaleido E-Ink EPD display.

I use a Pocketbook InkPad Color for USGS topo maps. They look pretty nice. Zooming is slow, because they are extremely complex vector PDFs on a low power device. I should probably try converting them to images to work around that problem. The screen is actually surprisingly tolerable for photos, too.

Surely you should use bitmap tiles; you can either use a network server for unplanned locations or download tiles beforehand for planned ones. Orux Maps offers the option.