What observers see optically with their eyes or with their optical instruments is not the main point of the Andromeda paradox at all.
The point to be understood is more along these lines: suppose you set up synchronized clocks all the way to Andromeda. Let's say for neatness you don't want it to be a long line of clocks, so set them in concentric circles of increasing radius $r$, from $r=0$ to $r=\infty$ (or just to a very distant $r=R_{\text{max}}$). All these clocks are stationary with respect to you.
Now suppose you actually do optically look at these concentric rings of stationary clocks, what do you see? Neglecting gravitational effects (we're talking SR only), the time it takes light to reach you from a clock sitting stationary at $r$ is $r/c$. Therefore you can tell yourself, "oh, all these distant clocks look more and more delayed relative to the ones that are closer. But that's okay, it's just that the light that left a clock sitting at $r$ is delayed by $r/c$. So, I'll just add $r/c$ depending on each clock's $r$ distance and that will allow me to verify, by comparing with my own local clock, that all of the clocks in my reference frame, are properly synchronized, i.e. that $t_{\text{local}}=t_{\text{r}}+r/c$, where $t_r$ is the time reading as received from a clock at a distance $r$.".
Now, having done that, how do you assign times to distant events? Easy! When an event happens some $r$ distance away, just look at the reading of the clock that's co-located with that event at $r$. The reading of this clock will ride essentially on the same light front as the event itself. No need to correct for the speed of light this time, because by construction we now know that 1. all our clocks are synchronized, and 2. the event and the light front carrying the reading of the clock occurred at the same spacetime point, and they both arrive to the same spacetime point where you're located.
So now after having done all that, you're basically set up with the necessary apparatus that constitutes an inertial reference frame, which you can already see involves more than just what you optically perceive. It allows you to assign times for distant events. Essentially, we have defined a notion of simultaneity for our inertial reference frame.
Now here's the real crux of the issue: you're inertial. Being inertial means being non-special, ergo, every inertial observer moving relative to you must be able to carry out the above procedure, and their results are completely valid in their reference frame. That's a key point: there really is no absolute meaning to simultaneity, and this is a direct consequence of the non-existence of any preferred reference frame.
But now to see a bit how that plays out, let's have a second inertial observer, moving relative to you, carry out the same procedure outlined above.
When you look at their concentric clock rings, you see that they don't agree with your clocks. What you see in fact, is that the other observers' clocks that are to their rear ("rear" - relative to their direction of motion) seem to be ahead of the clocks that are to their front (you'll also see that the circles of clocks are somewhat squished in their direction of motion, but that's a less important effect here). It has to be that way if you put a little thought into it: the observer moving relative to you is rushing towards the light signals coming from the clocks to their front, and "escaping" the ones coming from the clocks to their rear. So when they add their $r'/c$ value, for example to a rear clock to verify it is synchronized with their local clock, it seems they're adding a value that's "too small" because the actual distance light had to travel, according to you is larger than $r'$, so this is compensated by the fact that rear clocks are ahead. In other words, the $r'$ that the other observer uses is "too small" but the received time $t'_{r'}$ from a clock they see is "too big" (ahead), so the two effects compensate and the other observer hence always determines their clocks to be in synchrony, by comparing $t'_{r'}+r'/c$ to their local clock like you did.
For emphasis, the above analysis is all done according to what you see and measure the other observer is doing. The other inertial observer always sees that their concentric clocks are perfectly synchronized, and instead sees that your clocks are "out of whack" in a precisely symmetric manner.
So I hope all the above explains what we're talking about when we say that "observers" can be at the same place and yet assign different times to the same events. Now if you got all that, answering what happens when one observer suddenly comes to a stop is very simple: they are just "adopting" the measurements that were already done in the other frame. They discover that this is the only, or at least quickest way to set up a new reference frame, because now that they changed their velocity, the previous concentric clocks can no longer serve them: they will indeed see also that the "old clocks" that are all on the same $r=R$ are not synchronized. They can either synchronize them, or just adopt the other frames' clocks, which amounts to the same thing practically (and mathematically).
Why did it happen that when they came to a stop, suddenly their own clocks appear to be not synchronized properly? Very simple: recall that the initial synchronization procedure was done in a different inertial reference frame! So this is nothing else but what we've already explained: seeing their own "old clocks" being out of sync, is due to precisely the same reasons as seeing another inertial observers' clocks, moving relative to them, as out of sync. So nothing new has happened here.
Now in there lies another question you may ask yourself: how would one inertial observer measure the events involved in another inertial observer's synchronization procedure? I'll let you work out that one for yourself! It can be a great application of the principles I've tried to outline here.
