What do line colors in git log --graph mean?

The colors are merely meant to help you view the lines as distinct from other lines. To answer question #1, they are assigned not pseudo-randomly, but rather sequentially, each time git log --graph picks a new "column number". Unfortunately there are two issues I know of. Both tie into your question #2.

Here is the full list of colors by name:

    GIT_COLOR_RED,
    GIT_COLOR_GREEN,
    GIT_COLOR_YELLOW,
    GIT_COLOR_BLUE,
    GIT_COLOR_MAGENTA,
    GIT_COLOR_CYAN,
    GIT_COLOR_BOLD_RED,
    GIT_COLOR_BOLD_GREEN,
    GIT_COLOR_BOLD_YELLOW,
    GIT_COLOR_BOLD_BLUE,
    GIT_COLOR_BOLD_MAGENTA,
    GIT_COLOR_BOLD_CYAN,

Visually, many of these colors "look the same" (or similar enough to be kind of indistinguishable). In particular, I find that the "bold" ones look too much like the "regular" ones unless there are quite a few letters printed in "bold", i.e., my Mac Terminal font's "bold" is just not that much bold-er than its standard-weight. This makes many lines overly visually similar in the graph for git log --graph --decorate --oneline --all run on the Git repository for Git, for instance.

Edit: this is now fixable (or work-around-able), as of Git 2.12, using the new log.graphColors configuration entry. This is a comma separated list of color names or color numbers (see the git config documentation entry for "color" in the Values section).

Second, the "column number" is, currently, not actually the column number of the line. Instead, it's the column number of the commit. The line color goes up from that commit, to the commit above it. All the magenta lines in your image snapshot go to commits printed in column #0: both a55fd8d and 3c1494a are in "column 0". (They are both merge commits so they consolidate incoming lines.)

Is it possible to ask git to choose colors wisely to avoid isolated (not having common commit) same color lines to overlap?

You can always clone the Git repository for Git and write new code. I will note that the existing graph.c is nearly 1400 lines long, though.

In this commit 73c727d69f47572bf7f21fa31831f9a3fdad944c ("log --graph: customize the graph lines with config log.graphColors", 2017-01-19), it's possible to choose the colors with the log.graphColors config.

Even with standard terminal, if your background color is neither black or white, then the graph line may match your background and become hidden. You can exclude your background color (or simply the colors you hate) with this.

I use Git Bash and I exclude GIT_COLOR_BLUE color for above reason.

I can use any hex color codes (at least on Git Bash). Below config setting uses only three colors.

[log]
    graphColors = "#ffffff",red,green