CO2 tastes good! Carbonated water is actually a weak carbonic acid solution; this is what you taste. It's like "salt and pepper", but for water.
Slightly acidic water is usually popular, hence lemon juice is sometimes used to taint a jug of water in times when no carbonated water is available.
Carbonated water releases CO2 bubbles for many minutes after pressure is released (dissolved carbonic acid reforming), which is an important presentation effect that other gases do not generally have.
In many countries the local water supply is slightly alkaline (due to limestone rock being very common), and this can leave a bad after-taste, and make food in your mouth taste soapy. The addition of weak acids to water helps with neutralising this effect.
Around the world, some lucky towns have natural springs with effervescent water (carbonated water), and man-made carbonated water is just imitating this. In history people have often travelled great distances to try effervescent water, so its popularity is well recorded.
Nitrogen is used for water pressurisation in brewing and cooking as it leaves little or no taste, and generally does not form other chemical compounds. It's used mainly when bubbles are required, but not an acidic taste.
Oxygen is unsuitable for water pressurisation as very little can be dissolved at normal soda pressures, and it has no taste, but may readily form unwanted chemical compounds.
In the 18th century, Joseph Priestley was the first person to document this manufacturing discovery. He noted precisely that it tasted good, and that it was similar to the German Selters water. He was discovering "airs" (gases), and uniquely identified quite a few different gases. CO2 was the only one he listed as tasting good. His cheap source of CO2 was the fermenting grains from the nearby brewery.