Different monitors in my house are 1920x1080 (living room TV, which functions as a computer monitor when we set it to 'video 3'), 800x600 (specialized 'camping trip' laptop with 9-hour battery life and 3 days worth of backup batteries), 1280x1024 (regular laptop for use in more civilized areas where power is easier to find), and 2560x1600 (Main desktop machine, WXGA rotated 90 degrees for portrait aspect ratio rather than landscape).
I cannot imagine any single resolution and font size that would be appropriate on all these monitors.
It sounds like you're already committed to a much more graphical approach, but seriously, what's wrong with a plain-old-curses interface? The advantages are that the font will have already been set to a usable/visible size for that monitor (and can readily be reset by the user), you don't have to worry about scaling blurs, and your game is more portable.