The first widely recognized color graphics card for the IBM PC was the Color Graphics Adapter (CGA). It could produce 16 distinct colors. Not necessarily displaying them all at the same time, but still. And, for the sake of sanity, I'll ignore things like NTSC color hacking and dithering through the use of block graphics. This 16-color palette carried over into EGA with minor adjustments, and from there carried over into VGA.

VGA 16-color matrix
EGA and VGA allow the palette to be reprogrammed, but this was hardly ever exercised by users or programs. (DOOM's SETUP.EXE included a change of blue to a dark shade, but that is about the extent I remember outliers.)
Outside the PC world, there were of course the Unix workstations. The Sun CG2 card (1985) was capable of 256 simultaneous colors/16.7 million distinct ones. It appears that xterm only started supporting a color palette in 1996 (project color_xterm).
A turn for the worse
Many programs have been written with a basic assumption about
what colors the palette will contain. In fact, the ECMA-48 specification (2nd Ed., 1979, page 41 (PDF page 49)) even has
formalized what effect escape codes like \e[33;44m should
have.
In more modern times, people have come up with plenty of alternate palettes/color schemes for use with terminal programs. Many of these schemes were seemingly designed with an utter disregard for certain color pairings. Programs with background fill, such as exercised by Midnight Commander, look like hot neutron star garbage in many of these palettes. For example, the stock configuration of gnome-terminal/xfce4-terminal comes with "Tango", "Solarized", and the classic "VGA" palette. Activating each of these palettes produces these visual results:

MC with "VGA" palette

MC with GNOME's "Tango" palette

MC with GNOME's "Solarized" palette
Speaking of ECMA-48, "Solarized" is in violation, because 1;33 is not producing anything ordinary humans would consider "yellow". Tango still adheres to that specification, but intuitively has worse legibility than the VGA palette.
Let's quantify how various palettes perform. In the process of
conducting these analyses, I have constructed the palcomp utility (part
of the consoleet-utils package). An overview of the used palette on a
terminal with `palcomp ct`:

VGA

Solarized
From here on, I will leave out the Tango scheme, because it's just sort of a midpoint between VGA and Solarized.
Trivial contrast analysis
Legibility depends on a handful of factors; a prominent one is contrast, i.e. the difference in luminance or color. (Other factors could be text size or thickness, both of which are not relevant, since the focus in this document is on fixed-font terminal use.)
A first indication of how luminance influences legibility can be obtained by turning our images of the color tables to grayscale. This can be done with image manipulation programs. They have various algorithms; the venerable Paint Shop Pro version 5 from the Windows 9x era utilizes a quite inaccurate RGB-to-YCbCr transform[1], whereas GIMP uses a sRGB(BT.709)-to-CIELAB conversion[2].
[1] RGB-to-YCbCr conversion with BT.601 coefficients, using a somewhat
well-known formula: Y := 0.299*r + 0.587*g + 0.114*b
[2] e.g. L := 116*(0.212*r^2.4 + 0.715*g^2.4 + 0.072*b^2.4)^0.333 -
16
(this is not the full formula, but an abbreviated metric for people who like
trying things out)
This is the output from GIMP:

VGA converted to gray

Solarized converted to gray
A few things become apparent:
1. Pairings with low legibility in color (e.g. cell "26" in VGA also have low legibility in gray.
2. Pairings with moderate legibility in color (e.g. cell "29"
in VGA) may have less legibility in gray. (Colored fg/bg having higher
legibility is known as the Helmholtz–Kohlrausch
effect).
To support users with partial/full colorblindness, color should largely
be ignored when computing overall usability scores.
Using the palcomp cxl command, a contrast
analysis based on CIELAB lightness value differences between foreground and
background color can be produced. (To get the best visual reporting effect, do
also set the terminal to use the same palette.)

Lightness-based contrast analysis for VGA

Lightness-based contrast analysis for Solarized
Summing up those numbers gives an indication about the
palette's general contrast performance. The last three lines of the CXL
analysis printout offer scores for different grid subsections. This allows for
comparing palettes for slightly different blocks, while remaining general. For
example, few Linux programs exercise intense backgrounds (ECMA-48 codes
\e[100m to \e[107m) directly, so perhaps you want to
judge a palette just by the 16×8 metric. Some palettes may have been designed
with very limited scope, e.g. syntax-highlighted code blocks shown on HTML
pages seldomly use foreground intensity, so may warrant to be judged by the 8×8
matric. On the other hand, text selection in the terminal/editor/browser/etc.
may use trivial fg–bg inversion, making it necessary to judge even a limited
palette by the full 16×16 metric.
When a fg–bg color pair is below a certain threshold (cutoff currently at 7.0), that pair is essentially a lost cause and treated as 0 ("penalized") for the second sum.
Contrast analysis with APCA
Raw luminance is an important factor, but not the only
factor for legibility. With self-experimentation, I noticed that
white-on-anything (e.g. cells 07, 17, 27, etc. in the table printed by
palcomp ct) subjectively feels to have ever-so-slightly better
contrast than anything-on-white (e.g. cells 70, 71, 72, etc. in the
ct table; bottommost row of the cxl table). It seems
that the white background "bleeds" onto the text and diminishes the
contrast.
Researches have indeed independently came to the same conclusion in a relatively new contrast metric, APCA. APCA gives background colors a certain "boost" to account for the very phenomenon I intuitively had noticed. (APCA also takes font size and thickness into account, but as stated earlier, this is irrelevant to our fixed-font terminal usecase.)
palcomp has a cxa command which will compute
APCA. The contrast ratings for individual fg–bg color pairs are a bit different
from cxl, but overall, it generally follows CXL.

APCA contrast analysis for VGA

APCA contrast analysis for Solarized
Scores for various palettes
With these tools in hand, the CXL/CXA scores can be computed for a whole set of palettes. The termux-styling package has heaps of palettes to look at and see how they stack up against each other.
| cxl16×16 | cxl16×8 | cxa16×16 | cxa16×8 | name |
|---|---|---|---|---|
| 2343 | 1283 | 2711 | 1477 | gruvbox-material-dark-* |
| 2707 | 1490 | 3080 | 1778 | tokyonight-day |
| 3000 | 2200 | 3209 | 2346 | white-on-black |
| 3037 | 1519 | 3226 | 1613 | gruvbox-material-light-* |
| 3195 | 1586 | 3604 | 1751 | catppuccin-latte |
| 3832 | 1965 | 3734 | 1778 | base16-embers-* |
| 3240 | 1666 | 3875 | 1986 | catppuccin-frappe |
| 3527 | 1783 | 3929 | 1829 | base16-solarized-dark |
| 3785 | 1897 | 3947 | 1798 | base16-marrakesh-* |
| 3743 | 1911 | 3952 | 1838 | base16-atelierlakeside-* |
| 4026 | 2060 | 4265 | 2006 | base16-atelierheath-* |
| 4025 | 2261 | 4379 | 2349 | iceberg |
| 4033 | 2116 | 4414 | 2183 | base16-chalk-* |
| 3990 | 2083 | 4476 | 2274 | base16-one-dark |
| 3699 | 1898 | 4477 | 2283 | catppuccin-macchiato |
| 3930 | 2168 | 4481 | 2561 | rosé-pine-dawn |
| 4190 | 2167 | 4492 | 2159 | base16-atelierforest-* |
| 4265 | 2263 | 4540 | 2322 | tokyonight-dark |
| 4037 | 2195 | 4629 | 2389 | base16-ashes-* |
| 4197 | 2220 | 4636 | 2640 | gruvbox-light |
| 4555 | 2249 | 4707 | 2243 | base16-codeschool-* |
| 4217 | 2231 | 4756 | 2344 | gruvbox-dark |
| 4301 | 2209 | 4871 | 2326 | base16-atelierdune-* |
| 4775 | 2460 | 4900 | 2383 | base16-apathy-* |
| 4265 | 2225 | 5095 | 2564 | base16-mocha-* |
| 4146 | 2121 | 5133 | 2609 | catppuccin-mocha |
| 5087 | 2615 | 5258 | 2899 | base16-one-light |
| 4974 | 2544 | 5344 | 2560 | base16-grayscale-* |
| 4974 | 2544 | 5344 | 2560 | e-ink |
| 4881 | 2524 | 5347 | 2568 | base16-atelierseaside-* |
| 4539 | 2479 | 5375 | 2776 | base16-tomorrow-* |
| 4539 | 2479 | 5375 | 2776 | tomorrow-night |
| 5299 | 2750 | 5448 | 2671 | base16-greenscreen-* |
| 4531 | 2398 | 5454 | 2787 | base16-eighties-* |
| 4844 | 2793 | 5494 | 2994 | base16-bright-* |
| 4550 | 2431 | 5519 | 2906 | rosé-pine-moon |
| 4988 | 2638 | 5535 | 2725 | base16-brewer-* |
| 4636 | 2411 | 5569 | 2791 | base16-ocean-* |
| 4885 | 2545 | 5644 | 2814 | base16-paraiso-* |
| 4897 | 2541 | 5665 | 2781 | base16-google-* |
| 5084 | 2736 | 5818 | 2994 | base16-harmonic16-* |
| 4756 | 2557 | 5823 | 3061 | base16-flat-* |
| 4943 | 2678 | 5867 | 3101 | base16-bespin-* |
| 5261 | 2260 | 5960 | 2392 | base16-solarized-light |
| 5261 | 2515 | 5960 | 2848 | solarized-* |
| 5600 | 2800 | 5990 | 2995 | black-on-white |
| 4742 | 2439 | 6019 | 2968 | base16-materia |
| 4692 | 2706 | 6020 | 3350 | rydgel |
| 4987 | 2538 | 6158 | 3108 | nord |
| 5279 | 2856 | 6239 | 3307 | rosé-pine |
| 5764 | 2957 | 6439 | 3152 | base16-summerfruit-* |
| 6105 | 3532 | 6476 | 3519 | spacemacs |
| 5354 | 2798 | 6540 | 3330 | base16-railscasts-* |
| 5240 | 2620 | 6622 | 3310 | wild-cherry |
| 5697 | 2806 | 6697 | 3235 | material |
| 5836 | 3044 | 6790 | 3409 | base16-default-* |
| 6060 | 3159 | 6806 | 3328 | gnometerm-new |
| 5413 | 2916 | 6925 | 3634 | base16-snazzy |
| 5772 | 2928 | 7019 | 3406 | base16-twilight-* |
| 5596 | 3019 | 7044 | 3718 | base16-monokai-* |
| 6245 | 3260 | 7129 | 3697 | neon |
| 6198 | 3248 | 7174 | 3469 | smyck |
| 6157 | 3317 | 7238 | 3755 | dracula |
| 6092 | 3012 | 7334 | 3450 | ubuntu |
| 7529 | 3629 | 7399 | 3575 | gotham |
| 6399 | 3191 | 7438 | 3489 | nancy |
| 6494 | 3415 | 7628 | 3824 | base16-colors-* |
| 6727 | 3478 | 7635 | 3679 | gnometerm (tango) |
| 6619 | 3574 | 7805 | 4016 | base16-isotope-* |
| 6645 | 3459 | 7857 | 3902 | base16-3024-* |
| 6632 | 3441 | 7870 | 3951 | base16-londontube-* |
| 7216 | 3647 | 8084 | 3922 | base16-shapeshifter-* |
| 7526 | 3912 | 8653 | 4156 | zenburn |
| 7096 | 3662 | 8686 | 4378 | argonaut |
| 7980 | 3957 | 9061 | 4082 | VGA (palcomp vga) |
| 8055 | 3894 | 9133 | 4023 | VGA saturated (palcomp vgs) |
| 8294 | 3905 | 9145 | 3873 | xterm-R6-sb_right-ansi-3d (1995); 16c |
| 8563 | 4261 | 9468 | 4301 | Windows 3.0 (palcomp win, termux:e-ink-color) |
| 8423 | 4299 | 9669 | 4679 | XFree86 3.1.2e xterm (1996; T.Dickey) |
There is no way to sugercoat it; almost all of the modern palettes are terrible for use as a generic palette that needs to cover all use cases. The winners, instead, all almost directly relate the vivid classic CGA palette.
Optimal palette
The lightnesses of the colors can be placed in equidistant
steps, which should give the largest lightness differences between any color
pair, thus maximizing the CXL score. To that end, the palcomp eq
and palcomp loeq commands can be used. When we do this for all the
top runners they expectedly get the same rating (except for VGA in loeq mode,
which I should go diagnose):
| cxl | loeq cxl | eq cxl | name |
|---|---|---|---|
| 7980 | 8808 | 9094 | VGA |
| 8150 | 9002 | 9094 | VGA saturated |
| 8294 | 9002 | 9094 | xterm-R6-sb_right-ansi-3d 1995 |
| 8563 | 9002 | 9094 | Windows 3.0 |
| 8423 | 9002 | 9094 | XFree86 3.1.2e xterm 1996 |
To be continued... this article is not finished and warrants more elaboration, e.g. on the optical differences of equalized palettes, and whether (or not) the maximum CXL score has already been achieved. The darkest color has L=11, and the effects of preferring a higher minimum L of, say, 22, at the cost of some illegible pairs, should be looked at.
For the time being, VGA is a sane default palette ready for general use (not specific to any particular application or expectation beyond ECMA-48).