If you were at sea level (e.g. on a boat), the tower would disappear over the horizon at approximately 505km away.

Horizon calculations are generally dealt with as simple right-angle triangles; a tower meets the horizon at $d = \sqrt{t^2 + 2rt}$, where $t$ is the tower height and $r$ is the radius of the earth.
According to this site, the visual acuity of the human eye is about 1/60 of a degree. That means at a distance of 500km you could distinguish something about 150m tall/wide or bigger. So you likely won't see the top of the tower (at 100m) at this distance.
Working backwards, if the tower were a constant 100m wide it seems you would cease to be able to make it out at $d = x/(2\tan (1/120))$, which is 344km. The tower is actually tapered so it would likely be a bit further than that, but the maths gets more complicated.
Let's say for now that ignoring the atmosphere, the distance you could see the tower with the naked eye would be somewhere between 350km and 400km. This also answers question one: yes, if you were underneath the tower you could see the top (20km away) if there was no atmospheric scattering.
It's hard to find hard data, but various sources suggest the best-case distance when considering atmospheric scattering is perhaps about 160km. This is sufficiently far that the difference between looking at the top of the tower and the part touching the horizon is negligible. At a distance of 160km, the bottom 2km of the tower would be below the horizon.
At 20km, the top of the tower is in the mid-stratosphere, above cloud layer and in amongst the ozone layer. It definitely could be obscured by clouds, but if the sky was clear I don't think the atmosphere itself would be a problem. I'm struggling to find much data on that. It would possibly depend on the time of day and how well-lit the tower was.
One thing that occurs to me though is that there may be permanent cloud cover (see next paragraph) which could mean the top of the tower is never visible from the ground.
I imagine the temperature differential between the top and bottom of the tower might make for some interesting effects (condensation? Permanent cloud cover? Perhaps it could be used as some kind of heat engine?). Similarly, it might provide a useful nesting surface for sea birds, shade for fish etc.