Legibility is paramount. I agree with Ruby on the bigger labels, also, think hard on what's necessary and what's not in that department.

About the trimming down, it's a tricky question. You want your reader to have the information. It can be in the book, on the map or both but both is not a necessity. My advice would be to start with few texture elements, add them and see what it looks like in printed version at ebook size. The goal is to inform, not to obstruct and a no texture is better than too much. It has to be clear or have stark contrast that help legibility.

The two versions option is a good one IMO.