The first thing to note is that everything depends on the heuristic you use to order the vertices. On the one hand, if you knew an optimal coloring, you could get the greedy algorithm to produce it: just feed it all the vertices of one color, then all the vertices of another color, and so on. On the other hand, all known simple heuristics fail on some counterexamples.
Here are a few popular heuristics and their justifications.
Highest degree first
We are forced to use a new color when we get to a vertex and all previously used colors already appear on its neighbors. This is most likely to happen with high-degree vertices: if many of their neighbors have already been colored when you get to them, then you're likely to be forced to use a new color. So this heuristic goes through vertices from highest to lowest degree, to catch the high-degree vertices before many of their neighbors have been colored.
Adaptive degree counts
We can try to improve on the reasoning above. High-degree vertices are not a threat to start with: high-degree vertices gradually become more and more threatening as you color more and more neighbors. So we can take that threat measure into account instead, as we go:
- The incidence degree heuristic says that at each step, we color the vertex which has the most already-colored neighbors.
- The saturation degree heuristic says that at each step, we color the vertex with the largest number of distinct colors represented among its neighbors.
Lowest degree last
This is a trickier one which plans out the entire ordering in advance. Starting with an $n$-vertex graph $G$, we pick a vertex $v$ with the lowest degree, and put that one last. Then recursively apply this algorithm to $G-v$ to order the $n-1$ vertices that will come before $v$.
Part of the justification is the same: towards the end of the algorithm, when many vertices have been colored, we don't want to get stuck with a high-degree vertex such that all the different colors appear on its neighbors, because that's what will force you to use an extra color.
The other part of the justification for this heuristic is its guaranteed performance on some classes of graphs. For example, the lowest degree in a planar graph is guaranteed to be $5$ or less, and so this heuristic is guaranteed to color any planar graph with $6$ colors. More generally, it colors any $k$-degenerate graph with $k+1$ colors.