The telescope and timing part of this problem are actually relatively easy. You can align a fairly cheap telescope towards a star with an accuracy of about an arcsecond, which is a distance of about 30 metres on the earth's surface. Beyond that, the turbulence in the atmosphere tends to blur the view, so it is hard to get much more accurate.
One of those arcseconds passes by approximately 15 times a second, so using an atomic clock for that is way overkill - any time source more accurate than 1/15 of a second is unnecessary.
The main problem is that once you have aligned your telescope, now what you are trying to do is measure the direction of gravity, compared to the direction you're pointing the telescope, and that's a lot harder. Partly because that's a mechanical angle measurement (you need a pendulum that can freely swing and rest with minimal friction pointing directly in the direction of gravity, and then you need to measure angle). But then also, you need to take account of the fact that the gravitational field on the Earth is lumpy. If you're sitting next to a mountain, the gravitational field will be deflected slightly from pointing directly downwards - and in fact that was used a while back to measure the density of the Earth.
But theoretically, if you can solve the angle measurement bit, you could determine your location on Earth with an error of around 30m.
Yes. To a large extent, the positions of the stars are fixed with respect to each other. It's just the Earth that moves around. You're trying to get latitude, which you can get from the altitude of a star above the southern horizon, and longitude, which you get from when the star passes east to west. Choosing another star doesn't get you out of having to measure which direction is down. The "which direction is down" question is the answer to "where am I on Earth" - the telescope and timer are just there to set your frame of reference.
Sextants used at sea find altitude angles by measuring between the stars(or other astronomical objects) and the horizon. There is a correction that can be applied to account for wave height as it affects the "eye height." Azimuth can be found by measuring against stars that are low in the sky, but most of the time you do not need this for sea navigation. "Down" is inferred as the shortest path between a star and the horizon. It takes a bit of practice to get a good measurement from a rolling boat, but it is skill anyone can learn.
At sea the fact that "down" is perpendicular to the horizon is useful, because the horizon is pretty much a straight line. On land this is irrelevant because the horizon is rarely flat on land.
You would suspend your measuring apparatus in a device that absorbed or heavily dampened the motion of the waves (like gas struts, or something similar).
One of those arcseconds passes by approximately 15 times a second, so using an atomic clock for that is way overkill - any time source more accurate than 1/15 of a second is unnecessary.
The main problem is that once you have aligned your telescope, now what you are trying to do is measure the direction of gravity, compared to the direction you're pointing the telescope, and that's a lot harder. Partly because that's a mechanical angle measurement (you need a pendulum that can freely swing and rest with minimal friction pointing directly in the direction of gravity, and then you need to measure angle). But then also, you need to take account of the fact that the gravitational field on the Earth is lumpy. If you're sitting next to a mountain, the gravitational field will be deflected slightly from pointing directly downwards - and in fact that was used a while back to measure the density of the Earth.
But theoretically, if you can solve the angle measurement bit, you could determine your location on Earth with an error of around 30m.