See A city to last ten million years: Construction for background.
Second question:
What would be the best choice of site on the planet's surface? Assume the planet is more or less Earthlike in its climate, terrain and vegetation.
Also related: A city to last ten million years: Maintenance
Ten million years are long enough to worry about plate tectonics, climate shifts, and so on.
On top of something like Ayers Rock? A batholith? Or are they too likely to be mountainous?
I think you have a problem with assuming that the planet is earth like; Drop that and the situation becomes quite doable. If I were wanting to build a city that lasted ten million years my choice of location would be a planetoid that doesn't have a molten core and is geologically stable but large enough to have sufficient gravity so that the first generations are not inconvenienced by it.
As best as possible, ensure a stable orbit for the plant in question and then bore into it to its heavy metal rich core and build most of the support systems of the city deep in the interior powering the city with radioactive isotopes such as Uranium 235 (half-life of 700 million years). Leave the outer layers of the planet actually completely devoid of anything as a radiation and impact shield.
Of course, everything is going to have to be over engineered to be completely passive, as fool proof as possible, and automatic fail safes that depend on nothing themselves to function.
Which if the surface of the planet was also inhabitable, and earth like as specified but without active tectonics, then we get something like HG Wells Time Machine probably developing, actually quite possibly over multiple iterations over the time periods in question.
The building of the city itself would take long enough to, even if it didn't start this way, become a religion, and the city would last long enough that giants and gods were the builders of the city, even if the knowledge of how the city was built is not actually lost fully.
I don't think that this is possible in the face of technological regression. Key point here is that it has to remain habitable. That means that it has to have food and water supplies readily available for its occupants. When combined with climate shifts and geological events, this quickly becomes a huge issue. (Ok it quickly becomes a huge issue in planning, it may take thousands of years for the actual problems to manifest.)
Lakes, rivers, springs, and wells can all dry up or flood due to earthquakes and shifts in weather patterns. The change doesn't even have to be nearby. An earthquake that causes land hundreds of miles away to settle or raise can disrupt the flow of rivers and streams. New mountains and or volcanic activity along the coast will change the wind and rain patterns for the continent. What would be self sustaining farm land today may be a barren desert, or at the bottom of a sea/lake, in a couple hundred years.
Similarly, unless your planet has NO tectonic activity the ground will move and change. Building with your foundation in bed rock sounds like a good idea, until you realize that something that is flat now has a high chance of being anything but flat in one million years, much less several. (Anecdotally, there is a spot in Arizona along the highway between Phoenix and Flagstaff where they cut through a ridge rather than taking the road over it. It has stuck in my mind because you can see sedimentary rock with the bands running in 3 different directions, and distinct seams between the regions. I have never quite figured out what, but obviously something significant had to happen to the ground in that area for those layers to form the way they did.)
If the society retains enough technology to be able to import food/water supplies in the face a climate change and readjust their foundations after geological shifts, then this becomes potentially feasible.
