If you actually have conceptual ideas behind better looking menus and map viewing, go ahead and post because I'll be listening. If you want to yell about terminal sizes from the 80's, start another thread please.
Keep in mind that the reason you are having problems figuring out how to layout your menus and map view is due to the fact that you are constraining yourself to a small terminal size, so the responses about terminal size aren't totally unrelated since the obvious solution to the problem is to drop that constraint.
That said, I too prefer smaller terminal sizes since I do most of my roguelike gaming on a small linux netbook. While this device is certainly not from the 80's the screen size has led me to *not* play certain roguelikes in the past. For example, if I were to try out the previously mentioned The Ground Gives Way, which apparently requires a 92x38 terminal, I would have to reduce the font size to something pretty small to fit all 38 of the rows on screen. More likely, I'll just never play it because I have other awesome games which do run fine on my netbook.
One solution is to take an approach similar to what Angband does with the extra menus and windows it has when run in the terminal. On a large terminal, it displays extra information on the side of the main window (things like inventory, equipment, current monsters in view, etc). When played on a small terminal, those extra things are hidden, but available through an extra key press (ex. you can hit 'i' to make the inventory list appear in the main screen area). Perhaps the best solution to your problem is to simply hide the things which are not crucial to what the player is doing at any particular moment and make the extra info easily available through other means. The trick then becomes determining what information is crucial at any given moment, and what info is important enough to be easily accessible but not needed on the main screen.