(This section is largely due to David Kastrup <email@example.com>)
At a fixed dot clock, an interlaced display is going to have considerably less noticable flicker than a non-interlaced display, if the vertical circuitry of your monitor is able to support it stably. It is because of this that interlaced modes were invented in the first place.
Interlaced modes got their bad reputation because they are inferior to their non-interlaced companions at the same vertical scan frequency, VSF (which is what is usually given in advertisements). But they are definitely superior at the same horizontal scan rate, and that's where the decisive limits of your monitor/graphics card usually lie.
At a fixed refresh rate (or half frame rate, or VSF) the interlaced display will flicker more: a 90Hz interlaced display will be inferior to a 90Hz non-interlaced display. It will, however, need only half the video bandwidth and half the horizontal scan rate. If you compared it to a non-interlaced mode with the same dot clock and the same scan rates, it would be vastly superior: 45Hz non-interlaced is intolerable. With 90Hz interlaced, I have worked for years with my Multisync 3D (at 1024x768) and am very satisfied. I'd guess you'd need at least a 70Hz non-interlaced display for similar comfort.
You have to watch a few points, though: use interlaced modes only at high resolutions, so that the alternately lighted lines are close together. You might want to play with sync pulse widths and positions to get the most stable line positions. If alternating lines are bright and dark, interlace will jump at you. I have one application that chooses such a dot pattern for a menu background (XCept, no other application I know does that, fortunately). I switch to 800x600 for using XCept because it really hurts my eyes otherwise.
For the same reason, use at least 100dpi fonts, or other fonts where horizontal beams are at least two lines thick (for high resolutions, nothing else will make sense anyhow).
And of course, never use an interlaced mode when your hardware would support a non-interlaced one with similar refresh rate.
If, however, you find that for some resolution you are pushing either monitor or graphics card to their upper limits, and getting dissatisfactorily flickery or outwashed (bandwidth exceeded) display, you might want to try tackling the same resolution using an interlaced mode. Of course this is useless if the VSF of your monitor is already close to its limits.
Design of interlaced modes is easy: do it like a non-interlaced mode. Just two more considerations are necessary: you need an odd total number of vertical lines (the last number in your mode line), and when you specify the "interlace" flag, the actual vertical frame rate for your monitor doubles. Your monitor needs to support a 90Hz frame rate if the mode you specified looks like a 45Hz mode apart from the "Interlace" flag.
As an example, here is my modeline for 1024x768 interlaced: my Multisync 3D will support up to 90Hz vertical and 38kHz horizontal.
ModeLine "1024x768" 45 1024 1048 1208 1248 768 768 776 807 Interlace
Both limits are pretty much exhausted with this mode. Specifying the same mode, just without the "Interlace" flag, still is almost at the limit of the monitor's horizontal capacity (and strictly speaking, a bit under the lower limit of vertical scan rate), but produces an intolerably flickery display.
Basic design rules: if you have designed a mode at less than half of your monitor's vertical capacity, make the vertical total of lines odd and add the "Interlace" flag. The display's quality should vastly improve in most cases.
If you have a non-interlaced mode otherwise exhausting your monitor's specs where the vertical scan rate lies about 30% or more under the maximum of your monitor, hand-designing an interlaced mode (probably with somewhat higher resolution) could deliver superior results, but I won't promise it.