is it technically possible to accurately verify someone’s age while respecting their privacy and if so how?

With your constraints yes, but there are open questions as to whether that would actually be enough.

Suppose there was a well-known government public key P_g, and a well protected corresponding government private key p_g, and every person i (i being their national identity number) had their own keypair p_i / P_i. The government would issue a certificate C_i including the date of birth and national identity number attesting that the owner of P_i has date of birth d.

Now when the person who knows p_i wants to access an age restricted site s, they generate a second site (or session) specific keypair P_s_i / p_s_i. They use ZK-STARKs to create a zero-knowledge proof that they have a C_i (secret parameter) that has a valid signature by P_g (public parameter), with a date of birth before some cutoff (DOB secret parameter, cutoff public parameter), and which includes key P_i (secret parameter), that they know p_i (secret parameter) corresponding to P_i, and that they know a hash h (secret parameter) such that h = H(s | P_s_i | p_i | t), where t is an issue time (public parameter, and s and P_s_i are also public parameters. They send the proof transcript to the site, and authenticate to the site using their site / session specific P_s_i key.

Know as to how this fits your constraints:

Let the service know that the user is an adult by providing a verifiable proof of adulthood (eg. A proof that’s signed by a trusted authority/government)

Yep - the service verifies the ZK-STARK proof to ensure the required properties hold.

Not let the service know any other information about the user besides what they already learn through http or TCP/IP

Due to the use of a ZKP, the service can only see the public parameters (plus network metadata). They’ll see P_s_i (session specific), the DOB cutoff (so they’ll know the user is born before the cutoff, but otherwise have no information about date of birth), and the site for which the session exists (which they’d know anyway).

Generating a ZK-STARK proof of a complexity similar to this (depending on the choice of hash, signing algorithm etc…) could potentially take about a minute on a fast desktop computer, and longer on slower mobile devices - so users might want to re-use the same proof across sessions, in which case this could let the service track users across sessions (although naive users probably allow this anyway through cookies, and privacy conscious users could pay the compute cost to generate a new session key every time).

Sites would likely want to limit how long proofs are valid for.

Not let a government or age verification authority know whenever a user is accessing 18+ content

In the above scheme, even if the government and the site collude, the zero-knowledge proof doesn’t reveal the linkage between the session key and the ID of the user.

Make it difficult or impossible for a child to fake a proof of adulthood, eg. By downloading an already verified anonymous signing key shared by an adult, etc.

An adult could share / leak their P_s_i and p_s_i keypair anonymously, along with the proof. If sites had a limited validity period, this would limit the impact of a one-off-leak.

If the adult leaks the p_i and C_i, they would identify themselves.

However, if there were adults willing to circumvent the system in a more online way, they could set up an online system which allows anyone to generate a proof of age and generates keypairs on demand for a requested site. It would be impossible to defend against such online attacks in general, and by the anonymity properties (your second and third constraints), there would never be accountability for it (apart from tracking down the server generating the keypairs if it’s a public offering, which would be quite difficult but not strictly impossible if it’s say a Tor hidden service). What would be possible would be to limit the number of sessions per user per day (by including a hash of s, p_i and the day as a public parameter), and perhaps for sites to limit the amount of content per session.

Be simple enough to implement that non-technical people can do it without difficulty and without purchasing bespoke hardware

ZK-STARK proof generation can run on a CPU or GPU, and could be packaged up as say, a browser addon. The biggest frustration would be the proof generation time. It could be offloaded to cloud for users who trust the cloud provider but not the government or service provider.

Ideally not requiring any long term storage of personal information by a government or verification authority that could be compromised in a data breach

Governments already store people’s date of birth (think birth certificates, passports, etc…), and would need to continue to do so to generate such certificates. They shouldn’t need to store extra information.