First, note that by the time Andromeda is close enough for collisions with wandering stars to become a concern, Earth's average temperature will have changed significantly, and the planet will be unrecognizable.
When Sol is 8.5 billion years old, it will still have hydrogen available for fusion, but as it fuses it contracts and expands differentially. The contraction causes hydrogen fusion to become more favorable, so that Sol will have 50% greater power output ($6 \times {10}^{26}\ \mathrm{W}$) and 3% greater effective temperature ($6000\ \mathrm{K}$). Fusion also causes Sol to lose mass at a prodigious rate (currently $4 \times {10}^9 \mathrm{kg/s}$); it will release $6 \times {10}^{43} \mathrm{J}$ from fusion, which corresponds to $7 \times {10}^{26}\ \mathrm{kg}$. That is about one hundred Earth masses of sunlight but only $1 \over 3000$ the mass of Sol. Gravitation with Earth decreases proportionally, so Earth's orbit might on average expand $3000\ \mathrm{km}$ per billion years. Other gravitational effects might change Earth's average distance by as much as $6 \times {10}^5\ \mathrm{km}$, 4‰ of an astronomical unit. Expansion of Sol's outer layers due to reduced gravitation will increase its radius by 20%, $3 \times {10}^5\ \mathrm{km}$. Thus Earth will receive nearly 50% more power as well.
The energy balance of Earth wrt Sol gives the expected surface temperature:
$$
\begin{align}
\bar{a} = & 0.7 & \small\text{(Average absorption)} \\
P_p = & 1366\ \mathrm{W/m^2} & \small\text{(Average solar flux incident on Earth at present)} \\
P_f = & P_p \cdot 1.5 \approx 2000\ \mathrm{W/m^2} & \small\text{(In future)} \\
\sigma = & 5.670373 \times {10}^{-8}\ \mathrm{W/m^2/K^4} & \small\text{(Stefan-Boltzmann constant)} \\
\\
T_p^4 = & \frac{\bar{a} P_p}{4 \sigma} \\
\approx & \frac{0.7 \cdot 1366\ \mathrm{W/m^2}}{2.268149 \times {10}^{-7}\ \mathrm{W/m^2/K^4}} \\
\approx & 4.2 \times {10}^9\ \mathrm{K^4} \\
T_p \approx & 250\ \mathrm{K} \\
\\
T_f \approx & T_p \cdot {1.5}^{1/4} \approx T_p \cdot 1.11 \\
\approx & 280\ \mathrm{K}
\end{align}
$$
Since the average surface temperature on Earth is not $-20\ \mathrm{°C}$ — it is $+15\ \mathrm{°C}$ and already around $8\ \mathrm{K}$ warmer than in an airless future — we can see the atmosphere has a significant role in retaining heat. Assuming increasing cooling needs do not lead to the atmosphere retaining more heat, the average surface temperature can be expected to rise to $+50\ \mathrm{°C}$.
The average temperature of Antarctica is now $240\ \mathrm{K}$ in winter and $270\ \mathrm{K}$ in summer. These can be expected to rise to $270\ \mathrm{K}$ (just below freezing) and $300\ \mathrm{K}$ (well above freezing) respectively, and this is a best-case scenario. Antarctica will melt. That will produce the largest component (60%) of sea level increase, in total around $100\ \mathrm{m}$.
If Earth were still inhabited four billion years from now, it is extremely unlikely that Earth would fall into a star from Andromeda.
Space is big. Really big. You just won't believe how vastly, hugely, mindbogglingly big it is.
— Douglas Adams, The Hitchhiker's Guide to the Galaxy
The Milky Way is about 100,000 light years in diameter and contains about 400 billion stars. Andromeda is bigger and denser; it may have one trillion stars and a diameter of 140,000 light years. It is 2.5 million light years away but appears six times larger than Sol.
$$
\begin{align}
d_M \approx & \frac{4 \times {10}^{11}\ \mathrm{stars}}{{10}^{10} \pi/4\ \mathrm{{ly}^2}} \\
\approx & 50\ \mathrm{stars/{ly}^2} \\
\\
d_A \approx & \frac{{10}^{12}\ \mathrm{stars}}{2 \times {10}^{10} \pi/4\ \mathrm{{ly}^2}} \\
\approx & 60\ \mathrm{stars/{ly}^2} \\
\end{align}
$$
If the two galaxies were simply superposed, there would be about one hundred stars per square light year, viewed from infinitely far along the rotation axis. However, the Milky Way is a 2:1 ellipse as seen from Andromeda, while we see Andromeda as a 3:1 ellipse. Projecting both onto a plane between them, perpendicular to a line between their central black holes, would give a region of overlap with dimensions between $50 \times 50\ \mathrm{{kly}^2}$ and $50 \times 100\ \mathrm{{kly}^2}$, with at most half the Milky Way outside it. Sol is likely to be involved in the collision, since it is about 27,200 light years from the galactic center.
That doesn't mean, though, that Earth will come close to another star, that Sol might collide, or that the solar system will be disrupted.
Considering probabilistically the worst-case scenario (the entire Milky Way falls through Andromeda on their first pass), there is a mean free path for stars. The actual stellar density of the colliding galaxies is:
$$
\rho \approx 1.4 \times {10}^{12}\ \mathrm{stars}\ /\ V_{A \cup M}
$$
where the union of the two galaxies' volumes would be a very complicated expression. Very roughly, their volumes can be described as joined cones, ignoring their spheroidal dark matter halos (which are mostly harmless).
$$
\begin{align}
\rho \approx & \frac{1.4 \times {10}^{12}\ \mathrm{stars}}
{\left(
\frac{1}{2} \cdot
\left(
{10}^3\ \mathrm{ly} \cdot {10}^{10} \pi/4\ \mathrm{{ly}^2} +
1.4 \times {10}^3\ \mathrm{ly} \cdot 2 \times {10}^{10} \pi/4\ \mathrm{{ly}^2}
\right)
\cdot \frac{1}{3}
\right)} \\
\approx & 0.28\ \mathrm{stars/{ly}^3} \\
\\
V_\star \approx & 3.6\ \mathrm{{ly}^3} \\
\\
r_\star \approx & {\left( V_\star \cdot \frac{3}{4 \pi} \right)}^{1/3} \\
\approx & 0.95\ \mathrm{ly}
\end{align}
$$
At a distance of 1.9 light years, Betelgeuse would look a lot like Mars. If we assume disaster results from a star closer than the diameter of the heliosphere (about 200 AU), then:
$$
\begin{align}
m = & \frac{1\ \mathrm{star}}{\rho \cdot \pi \cdot 4 \times {10}^4\ \mathrm{{AU}^2}} \\
\approx & 1.1 \times {10}^{21}\ \mathrm{m} \\
\approx & 7.2 \times {10}^9\ \mathrm{AU} \\
\approx & 1.1 \times {10}^5\ \mathrm{ly}
\end{align}
$$
On average, a star can travel 110 thousand light years before it grazes past another, slightly less than the diameter of Andromeda. The proportion of stars from the Milky Way that do not approach within 200 AU of stars in Andromeda is at least $1/e^{1.4 / 1.1} \approx 100/400\ \mathrm{billion\ stars}$. For Earth to approach within 4 AU of another star (one Betelgeuse radius), it can be expected to travel at least 2500 times farther, which at a relative velocity of 300 km/s would take $9 \times {10}^{18}\ \mathrm{s} \approx 300\ \mathrm{billion\ years}$.
