My advice would be to go with the display mode that you feel most comfortable with. This greatly depends on whether the map is going to be bigger than the display or not, and how much information you need to display besides the map.
Personally, I would at least support 80x25, since this is the most widely supported full screen text mode. To allow square characters, I'd use 80x50. Screen 12 is actually a graphics mode which can be used as a text mode, so as long as 640x480 is supported, 80x30 or 80x60 will display fine. Screen readers are not going to work in this mode, though. But if your game runs okay in full screen, console window, and DosBox, I don't think you have to worry about future compatibility.
About 'converting' to another screen mode; it could be worth your while to write some display routines that handle different display sizes. Ages ago, I wrote a view object in Pascal which defined four panels (message bar at the top, status bar at the bottom, map view at the left, and info display at the right), each of which could be set to any width, height, and position.