When, and where, was the earliest record of non-Euclidean geometry? It was always my impression that Riemann created them, but did it really take that much time for someone to try to create an alternate system of mathematics?
Technically, the first was Lobachevski (published in 1829-30). Bolyai was independent (published in 1832). Gauss discovered it independently of both (not published).
A more complicated research is needed to find out when it was actually discovered by each person, and we can never be 100% sure of the result. Perhaps Gauss was the first. But the usual way to establish priority is the date of publication.
All three discovered ONE non-Euclidean geometry (hyperbolic geometry). Riemann's contribution was a more general approach, introducing infinitely many possible geometries (Riemannian geometry).
Usually this is attributed to, in alphabetical order, Bolyai, Gauss, and Lobachevski all working at about the same time in the first third of the 19th century. This certainly predates Riemann.
A colorful Harvard mathematician and guitarist Tom Lehrer seems to suggest in one of his songs that Lobachevski was guilty of plagiarism. However, In the liner notes to his album "The Tom Lehrer Collection" about the song "Lobachevsky," Lehrer wrote this: "Incidentally, Nicolai Ivanovich Lobachevsky (1793-1856) was a genuine mathematician, best known for his development of non-Euclidean geometry. His name was chosen here solely for prosodic reasons and was not intended as a slur on his character."
Further discussion can be found at this post where it transpires (in a deleted answer) that Gauss wrote a letter on non-Euclidean geometry in 1824, i.e., six years before Lobachevski published. Similarly Bolyai was apparently already working on the problem in the early 1820s. The fact that Buniakovski was sent to study with Cauchy in the early 1820s indicates that Russia was aggressively pursuing contacts with the West at the time. Furthermore both the other page linked above and other internet sources indicate that there do exist historians who hold that Lobachevski may have plagiarized his results, but the views of these historians are rejected out of hand without being discussed. I haven't seen this first hand but if someone can come up with a reference one could check the reliability of publisher/author/etc.
It should be mentioned that earlier work by Saccheri in the 17th century and Lambert in the 18th came very close but since it was thought inconceivable that the postulate might be independent such a conclusion was never pursued.
Regarding first developments in non- euclidean geometry, Eugenio Beltrami considered Lobachevsky-Bolyai geometry as nothing else but euclidean geometry on a space with (constant) negative curvature. In 2 memoirs published in 1868 he proposed some realizations of such geometries: one by using geodesics on a pseudosphere and others, including what is now known as the Beltrami-Klein model. He also gave a proof of equiconsistency of the Euclidean and hyperbolic geometry.