Having a mini-map is a great aid to most games, and it's come to be something people take for granted. Yet most of these same people will have trouble navigating a numbered street/numbered avenue city grid.

Anyways, I think a check-box at the beginning is a pretty good way to address many of the arguments against the cartography skill/mini-map issue. Those who find it a major deal can check (or uncheck, whatever), and get their mini-map without having to spend skill points/spend gold on a trainer. Those of us who don't find it that big of deal, or are willing to work with it, can just continue.
I do think having a trainer at the beginning town (without a very difficult quest/etc.) would help a lot. perhaps even some sort of reduced trainer, where they can only train one level (or, say, get a level from studying maps in a library, whatever). Maybe also mention this in the character creation screen about the cartography skill description. This was one of the issues I had in the first game, I spent a point (3 actually..) on it, only to find out that with a bit of patience, I could have saved myself 3 skill points for the cost of 100 gold. (but, far from game breaking, or even ranting about, I just didn't spend the points on cartography w/ my next character).