Answer. $98$.

Set $n = 100$.

1. We will show how to construct a polynomial $g$ of degree at most $n-2$ for a given polynomial $f$ of degree $n$. Multiplying $f$ by a nonzero constant doesn't change the condition (we can multiply $g$ by the same constant), so we assume the leading coefficient of $f$ is $1$, i.e., $f(x) = x^n + a_1 x^{n-1} + \dots + a_n$.

Take any set of $n$ distinct numbers $x_1, \dots, x_n$ whose sum is $-a_1$, and define $h(x) = (x - x_1) \dots (x - x_n)$, $g(x) = f(x) - h(x)$, so $h = f - g$.

We see that $f$ and $h$ have identical coefficients for $x^n$ and $x^{n-1}$, so the degree of $g$ doesn't exceed $n-2$. On the other hand, the $x$-coordinates of intersection points of $f$ and $g$ are exactly the roots of $h$, of which there are exactly $n$.

2. We'll show that $k \le n-3$ doesn't work. Let $f(x) = x^n$, and $g(x)$ be a polynomial of degree at most $n-3$. Suppose the graphs of $f$ and $g$ intersect at $n$ points with $x$-coordinates $x_1, \dots, x_n$. Then the polynomial $f-g$ of degree $n$ has $n$ real roots $x_1, \dots, x_n$.

However, $f-g$ has zero coefficients for $x^{n-1}$ and $x^{n-2}$. By Vieta's formulas, the sum $s_1 = x_1 + \dots + x_n$ and the sum of pairwise products $s_2 = x_1 x_2 + x_1 x_3 + \dots + x_{n-1} x_n$ both equal $0$.

Thus $x_1^2 + \dots + x_n^2 = s_1^2 - 2s_2 = 0$, which implies $x_1 = x_2 = \dots = x_n = 0$, contradicting the distinctness of the $x_i$.