It is hard to imagine painting without blue yet in prehistoric times there was none. By the time of Egyptian and Chinese cultures there was only Azurite or fugitive plant dyes like Indigo or smalt (blue glassy ceramic ground up). Ultramarine was a little more recent but it was rare due to cost. It was the 18th century that saw the start of our familiar blues. Prussian came first, then Cobalt, then synthetic Ultramarine. The 20th century brought Pthalocyanine and numerous new Cobalts so that we now have almost too many choices. If I had to choose one it would be a toos up between Ultramarine and Pthalo, probably the Ultra.

For a full list of pigments, see: Artists Pigments.