In 2000, the NY Times arbitrarily went with Red for Republicans because the first letter matched. This was the first time they printed color maps for an election. Everyone else kinda just went along with what the NY Times was doing that year.
And yeah, like you say CNN was showing that map a lot in 2000 and once people started saying “red state” and “blue state” it kinda stuck.