M-x list-colors-display shows all the valid color strings Emacs knows about in the current session.
Standard GUI Emacs and newer terminals like Alacritty can show All the colors (16 million), these are hex codes. Not all of them are named, but each name is associated with one hex color.
The 256 column is for terminals/displays that only show 256 colors, like gnome-terminal (i think. xterm-256color is a common terminal type for compatibility). These are named but the actual visual color values are set in the terminal config.
Likewise, 16 refers to original 16 color displays of later physical terminals. This is about the lower limit of colors to define for a visually distinct theme, for in my opinion. On some terminals/systems, the "bright" variants (8-16) are implemented as bolded forms of colors 0-7 respectively.
An example of an 8 color display is the Linux console, which you can reach with ctrl+alt+f4 or other function key between 2 and 6 inclusive on most Linux systems. Emacs does not look good on this display in most cases, but it's usable.