Coins in the right conditions last two thousand years easily (I collect ancient coins, have some that are 2500 years old that are in excellent condition). I expect in the right conditions some would last a few hundred million years. There's plenty of other non-biodegradable, chemically inert, discoverable things like stainless steel tools, gold jewelry, and other artifacts that humans make that could easily persist for millions of years.
As soon as coins appear in a geologic stata they become the most common archaeological artifacts found from humans, and at this point we've got hundreds of billions of them spread all over the globe with many becoming lost in spots where even if they were submerged in water, they could easily still remain intact for hundreds of millions of years. Not all coins are inert, but many are, and many really are going to stick around millions of years. While volcanic heat and pressure can mangle inert metals, not many other natural processes will. There's no magical entropy that would cause inert artifacts in geologically stable areas that some coins would wind up in to just lose their form magically. In our world today there's a lot of stainless steel, gold, and other inert artifacts that are going to persist for hundreds of millions of years. It's not like there's volcanoes everywhere, nor do tectonic plates subsume everything - we've got Cambrian fossils after all...
Depends on the sort of water, I guess. Salty and oxygen-rich wouldn't be so good. I'll just leave the https://en.wikipedia.org/wiki/Antikythera_mechanism here for you to think about. That had ca. 2100 years +/-ca. 100 years of underwater seawater exposure, and look what it did to it.
What would only 10000 years more of that have done to it?
That's bronze. I'd assume any brass/bronze/copper to corrode away, that's what it does naturally. Now consider gold, stainless steel, and the many other inert materials humans work with. I assume 10,000 year old gold artifacts would look the same as the 5000 year old artifacts we know of which are very well preserved, and other similar materials would fare similarly.
A million is a mind bogglingly large number, especially in years. I honestly can not say eitherway if anything survives. Coins might end up as a lump of rock with slightly higher metal content than surroundngs.
It is a very long time, but we still do have a lot of fossils, and with many human artifacts they won't fossilize so much as just sit there in their strata - we make artifacts that don't even need to fossilize since they are already stable, chemically inert, and resistant to biodegrading or corrosion, and if they do corrode, then in the right conditions those would be a kind of fossil. Ancient life made left lot of traces and humans are currently leaving as many traces as any other species has ever left, and we're leaving artifacts and other traces spread all across the globe, even in the oceans. We have fossils from >3 billion years ago. Not everything subducts. There's existent areas of long term geology stability and those areas are as littered with human traces, artifacts, and other remains as anywhere else. I honestly can't imagine all traces of humanity being undiscoverable considering in 100 million years, in 400 million subduction and time will have erased a lot, but I'm pretty confident there would be quite a few discoverable traces if some future life form were to apply modern archaeological methods then, esp. given that the scale and scope of changes humans are making is massive and global. At the very least future paleontologists would see the effects of humans on their habitat in the fossil record of the ongoing mass extinction, but I expect much more would be discoverable than that.
There’s still a lot of room to hide in that “almost”. Continental shields in Canada and Australia haven’t been recycled into the deep Earth and we can still find geological features there that are billions of years old.
