So I have been looking into paper for some years originally as part of a tangent related to my term paper on snowball Earth around 3 years ago and I think I have found a fair amount of fascinating complexity to the issue as these categories aren't clear cut and there have been and no doubt will continue to be changing as science is always in fluxFirst things first the terminology "protist" is not scientifically useful as it serves as a waste bin taxa for Eukaryotes that aren't plants animals and fungi. It iis now well established by genetics that there are two major divisions among Eukaryotes one roughly corresponding to the "algae" that largely or more aptly suggest plesiomorphic possession of a chloroplast whereas the other major lineage are almost entirely heterotrophs. In more detail things become far more messy as there have been a number of independent secondary endosymbiosis events and there has been a large degree of convergent evolution losses of photosynthesis and even reaquisition of photosynthesis but this largely covers the basic split as those details are well beyond the scope of this discussion.As others have said there is very strong evidence that the split between the two original domains archaea and bacteria was a very early occurrence soon after life arose. Since speculation is forbidden I will not discuss what the oldest evidence for life on Earth is since scientists do not agree on this and probably never will however some more recent phylogenic estimates for when LUCA(the Last Universal Common Anscestor) suggest the split between the two crown group domains was around 3.4 Ga.with LUCA itself occurring before 3.9 Ga. The point is that neither bacteria nor archaea are older than the other they clearly show evidence of a shared common ancestor. This is a phylogenic estimate so dates should be interpreted carefully but for this far back in time it is likely the best we can do.
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6152910/pdf/emss-78644.pdf
For reference the origin of Eukaryotes has long been a hot topic of debate but we are starting to finally get firm answers since metagenomics enabled the sampling of "unculturable" microorganisms enough to realize that our culturing process was blinding us to the vast majority of life on the planet the so called "microbial dark matter" but metagenomics has been herder to gain acceptance due to its potential for contamination but thanks to a team of Japanese researchers performing a decade of extensive work to raise them in a controlled setting we can now have more or less direct proof that they are complex archaea which largely have obtained many genetic sequences previously only known in Eukaryotes.
https://www.nature.com/articles/s41586-019-1916-6
Point is we can much more confidently say Eukaryotes likely arose from complex anaerobic archaea which associated with or co opted with aerobic bacterium to survive in the now oxygenated world. The Phylogenetics study cited finds that LECA(the Last Eukaryotic Common Ancestor) likely occurred around 1.8 Ga but due to definitively Eukaryotic fossils we know it had to be before 1.6 Ga. This suggests a rapid evolutionary radiation of Eukaryotes.
It is also worth noting that modern cyanobacteria appear to share a last common ancestor around this time. This is particularly interesting as this is very close to the fairly precise radio-dating for one of the 3 major asteroid impacts since after the GOE event 1.849 Ga. Given the target rock was a shallow sea around the Supercontinent Nuna it is quite possible a mass extinction may have occurred though confirmation will be hard since unicellular organisms are hard to identify in the fossil record if they get fossilized at all yet alone after 1.8 billion years later where only the deep impact complex kilometers down below the initial crater surface remains.
Life on the surface is quite hard to gauge at the very least there are some ancient evidence for algae colonizing shallow waters around the continents over a billion years ago. Surface life fossils are far more recent from the Ordovician time frame. However the terrestrial fossil record has always been poor and there are a number of things which suggest there was something going on up on land earlier.
One is the recent confirmation that Horseshoe Crabs are indeed true arachnids since nearly all arachnids are terrestrial this raises a question of whether the ancestor of arachnids diverged underwater and independnetly came on land in every other lineage or whether they came from a last common ancestor that was adapted to terrestrial environments. This latter scenario has a fair amount of support since a combination of modern research of arachnids reveals widespread UV florescence among modern arachnids derived from the organization of features in their cuticle a trait also identified in modern horseshoe crabs and for fossil chelicerates including the extinct eurypterids. Given the likely plesiomorphic characteristic of this UV florescence which sprectrally peaks in wavelengths now blocked entirely by the Ozone layer it seems logical to favor the terrestrial origin for their common ancestor. Given the Ordovician appearance of horseshoe crabs and eurypterids this implies their common ancestor had to have predated this divergence. Thus it is possible there is far older terrestrial biosphere elements that haven't been discovered making an identification of when and where quite challenging to assess. Fungi are unfortunately too understudied to assess. And the distinction among eukaryotes may be mute given studies of plants and their closest relatives among multicellular green algae found that a key development in the algae closest to plants and plants themselves was horizontal gene transfer with a bacterium which gave them the ability to survive in air.
Such a trait transfer suggests prokaryotic probably life beat multicellular life to land anyways. But yeah evidence that far back in time is hard to get.