The "Euclidean" algorithm was also directly relevant to both plane geometry and astronomical calculations. Many of the relevant ideas were worked on by Plato and his contemporaries at the Athenian Academy, and then in the next generation by Eudoxus and his followers. (Unfortunately most of the precursors to the Elements have been lost.)
Fun fact sort of about the Chinese Remainder Theorem:
It appears to have been named after the fact that it appears in a medieval Chinese mathematical treatise. But it always reminds me of the fact that in old Chinese texts it is frequently necessary to determine a number given its remainders modulo 10 and 12.
Why? Because that is the formal way to record dates! It has been for more than 3000 years. There is a Chinese cycle of 10 sequence markers, the "heavenly stems", and a separate cycle of 12, the "earthly branches". Because Chinese characters have no real ordering (there are ordering systems, but only specialists would bother learning or using them), the stems and branches are traditionally used when you need to give arbitrary names to things. (Examples of this survive in modern Chinese -- the two parties to a contract are 甲方 and 乙方, after the first two celestial stems 甲 and 乙 -- but modern Chinese are likely to use Western letters like A and B for their arbitrary names.)
The stems and branches together form the cycle of sixty, from 甲子 (1-1, meaning one) up to 癸亥 (10-12, meaning sixty). The system is so old that instead of incrementing one place value at a time for a cycle of 120 the values of which can be easily calculated in your head, incrementing bumps both place values, so the value following 甲子 is 乙丑, 2-2, meaning two. What does 乙卯 refer to? Well, 乙 is 2 (of 10) and 卯 is 4 (of 12). A little work with the Chinese Remainder Theorem will get you there!
Astronomy had no applications for centuries (unless you count astrology but do you really want to go there?). Saying that mathematics applies to it is disingenuous in the context of a discussion around the applicability of mathematics to the daily lives of an ordinary taxpayer.
Same goes for much of the theoretical work in geometry. Very little of it is applicable to daily life, with the notable exception of trigonometry and its uses in surveying and engineering.
But the results I was alluding to by mentioning Euclid were those from his work in number theory, including his namesake lemma and his proof of the infinitude of the primes, and the fundamental theorem of arithmetic. Those results had no application to daily life until the advent of modern cryptography.
It seems like you are unfamiliar with technology before the past few centuries. Beyond astrology (which was important!), people used these theoretical tools from geometry and number theory for time keeping, calendars, cartography, navigation, surveying (you mentioned), city planning, architecture, construction and analysis of machines, hydrology, water distribution, crafts such as metalworking and carpentry, accounting, optics, music, any kind of engineering involving measurements, ....
Obviously mathematicians were also excited about numbers and shapes for their own sake, and some of their activities (e.g. trying to square the circle or trisect an angle using compass/straightedge) were more like puzzles or games than engineering. But that doesn't mean the broad bulk of mathematics (even deductive proof-based mathematics) was practically worthless. Some of the most famous mathematicians of antiquity were also engineers.
Fluency with prime numbers per se (and prime factorization) is pretty useful when you are trying to do substantial amounts of (especially mental) arithmetic.
I'm not sure which "taxpayers" you are thinking about, but establishing an effective tax system and doing tax assessment and accounting is one example where having a more robust understanding of elementary arithmetic and number theory is pretty valuable. The development of the number and metrological systems and work on number theory in ancient Mesopotamia had quite a lot to do with tax accounting.
The "Euclidean" algorithm was also directly relevant to both plane geometry and astronomical calculations. Many of the relevant ideas were worked on by Plato and his contemporaries at the Athenian Academy, and then in the next generation by Eudoxus and his followers. (Unfortunately most of the precursors to the Elements have been lost.)