You should always use fixed-width fonts. The terminal is designed as a character-mode device emulator. Character mode devices use fixed-width fonts. There is little that can be done about this!
As a recommendation I would suggest you use either the font "fixed", or the font "10x20" as your default font (if the user is not allowed a choice). These are by far the cleanest and most readable of the smaller fixed-width fonts.
You may also like to use the courier fonts, but they aren't very readable unless they are larger font sizes.
Also remember that some users WILL have low-resolution displays (<=800x600). Please cater for such users by using a small, readable, and available font such as "fixed" as your default font.
If you give users an option to set the font, make sure they know that proportional fonts will not work correctly. Unfortunately there is no easy and general way to do this using the gnome or gtk font selector widgets. It may require an explicit check of the font before it is set in the terminal. If users are allowed to set arbitrary fonts then the display can become very ugly and distorted, but if they know this, then they can simply choose a fixed-width font.