Solution 1: We first prove the left hand side inequality. We begin by drawing an $n \times n$ board, with corners at $(0,0)$, $(n,0)$, $(0,n)$ and $(n,n)$ on the Cartesian plane.
Consider the line $\ell$ with slope $r$ passing through $(0,0)$. For each $j \in \{1, \dots, n\}$, consider the point $(j, \min(jr, n))$. Note that each such point either lies on $\ell$ or the top edge of the board. In the $j^{th}$ column from the left, draw the rectangle of height $\min(jr, n)$. Note that the sum of the $n$ rectangles is equal to the area of the board under the line $\ell$ plus $n$ triangles (possibly with area 0) each with width at most 1 and whose sum of the heights is at most $n$. Therefore, the sum of the areas of these $n$ triangles is at most $n/2$. Therefore, $\sum_{j=1}^n \min(jr, n)$ is at most the area of the square under $\ell$ plus $n/2$.
Consider the line with slope $1/r$. By symmetry about the line $y=x$, the area of the square under the line with slope $1/r$ is equal to the area of the square above the line $\ell$. Therefore, using the same reasoning as before, $\sum_{j=1}^n \min(j/r, n)$ is at most the area of the square above $\ell$ plus $n/2$.
Therefore, $\sum_{j=1}^n f_j(r) = \sum_{j=1}^n (\min(jr, n) + \min(\frac{j}{r}, n))$ is at most the area of the board plus $n$, which is $n^2+n$. This proves the left hand side inequality.
To prove the right hand side inequality, we will use the following lemma:
Lemma: Consider the line $\ell$ with slope $s$ passing through $(0,0)$. Then the number of squares on the board that contain an interior point below $\ell$ is $\sum_{j=1}^n \min(\lceil js \rceil, n)$.
Proof of Lemma: For each $j \in \{1, \dots, n\}$, we count the number of squares in the $j^{th}$ column (from the left) that contain an interior point lying below the line $\ell$. The line $x=j$ intersect the line $\ell$ at $(j, js)$. Hence, since each column contains $n$ squares total, the number of such squares is $\min(\lfloor js \rfloor, n)$. Summing over all $j \in \{1, 2, \dots, n\}$ proves the lemma. End Proof of Lemma
By the lemma, the rightmost expression of the inequality is equal to the number of squares containing an interior point below the line with slope $r$ plus the number of squares containing an interior point below the line with slope $1/r$. By symmetry about the line $y = x$, the latter number is equal to the number of squares containing an interior point above the line with slope $r$. Therefore, the rightmost expression of the inequality is equal to the number of squares of the board plus the number of squares of which $\ell$ passes through the interior. The former is equal to $n^2$. Hence, to prove the inequality, it suffices to show that every line passes through the interior of at least $n$ squares. Since $\ell$ has positive slope, each $\ell$ passes through either $n$ rows and/or $n$ columns. In either case, $\ell$ passes through the interior of at least $n$ squares. Hence, the right inequality holds. $\square$

Solution 2: We first prove the left inequality. Define the function $f(r) = \sum_{j=1}^{n} f_j(r)$. Note that $f(r) = f(1/r)$ for all $r > 0$. Therefore, we may assume that $r \ge 1$.
Let $m = \lfloor n/r \rfloor$, where $\lfloor x \rfloor$ denotes the largest integer less than or equal to $x$. Then $\min(jr, n) = jr$ for all $j \in \{1, \dots, m\}$ and $\min(jr, n) = n$ for all $j \in \{m+1, \dots, n\}$. Note that since $r \ge 1$, $\min(j/r, n) \le n$ for all $j \in \{1, \dots, n\}$. Therefore,
$$\begin{aligned} f(r) &= \sum_{j=1}^{n} f_j(r) = (1+2+\dots+m)r + (n-m)n + (1+2+\dots+n) \cdot \frac{1}{r} \\ &= \frac{m(m+1)}{2} \cdot r + \frac{n(n+1)}{2} \cdot \frac{1}{r} + n(n-m) \end{aligned} \quad (1)$$
Then by (2), note that $f(r) \le n^2 + n$ if and only if
$$\frac{m(m+1)r}{2} + \frac{n(n+1)}{2r} \le n(m+1)$$
if and only if
$$m(m+1)r^2 + n(n+1) \le 2rn(m+1) \quad (2)$$
Since $m = \lfloor n/r \rfloor$, there exist a real number $b$ satisfying $0 \le b < r$ such that $n = mr + b$. Substituting this into (2) yields
$$m(m+1)r^2 + (mr+b)(mr+b+1) \le 2r(mr+b)(m+1),$$
$$2m^2r^2 + mr^2 + (2mb + m)r + b^2 + b \leq 2m^2r^2 + 2mr^2 + 2mbr + 2br,$$
which simplifies to $mr + b^2 + b \leq mr^2 + 2br \Leftrightarrow b(b + 1 - 2r) \leq mr(r - 1) \Leftrightarrow b((b - r) + (1 - r)) \leq mr(r - 1)$. This is true since
$$b((b - r) + (1 - r)) \leq 0 \leq mr(r - 1),$$
which holds since $r \geq 1$ and $b < r$. Therefore, the left inequality holds.

We now prove the right inequality. Define the function $g(r) = \sum_{j=1}^{n} = g_j(r)$. Note that $g(r) = g(1/r)$ for all $r > 0$. Therefore, we may assume that $r \geq 1$. We will consider two cases; $r \geq n$ and $1 \leq r < n$.
If $r \geq n$, then $\min(\lceil jr \rceil, n) = n$ and $\min(\lceil j/r \rceil, n) = 1$ for all $j \in \{1, \dots, n\}$. Hence, $g_j(r) = n + 1$ for all $j \in \{1, \dots, n\}$. Therefore, $g(r) = n(n + 1) = n^2 + n$, implying that the inequality is true.
Now we consider the case $1 \leq r < n$. Let $m = \lfloor n/r \rfloor$. Hence, $jr \leq n$ for all $j \in \{1, \dots, m\}$, i.e. $\min(\lceil jr \rceil, n) = \lceil jr \rceil$ and $jr \geq n$ for all $j \in \{m + 1, \dots, n\}$, i.e. $\min(\lceil jr \rceil, n) = n$. Therefore,
$$\sum_{j=1}^{n} \min(\lceil jr \rceil, n) = \sum_{j=1}^{m} \lceil jr \rceil + (n - m)n. \quad (3)$$
We will now consider the second sum $\sum_{j=1}^{n} \min\{\lceil j/r \rceil, n\}$.
Since $r \geq 1$, $\min(\lceil j/r \rceil, n) \leq \min(\lceil n/r \rceil, n) \leq n$. Therefore, $\min(\lceil j/r \rceil, n) = \lceil j/r \rceil$. Since $m = \lfloor n/r \rfloor$, $\lceil n/r \rceil \leq m + 1$. Since $r > 1$, $m < n$, which implies that $m+1 \leq n$. Therefore, $\min\{\lceil j/r \rceil, n\} = \lceil j/r \rceil \leq \lceil n/r \rceil \leq m + 1$ for all $j \in \{1, \dots, n\}$.
For each positive integer $k \in \{1, \dots, m + 1\}$, we now determine the number of positive integers $j \in \{1, \dots, n\}$ such that $\lceil j/r \rceil = k$. We denote this number by $s_k$.
Note that $\lceil j/r \rceil = k$ if and only if $k - 1 < j/r \leq k$ if and only if $(k - 1)r < j \leq \min(kr, n)$, since $j \leq n$. We will handle the cases $k \in \{1, \dots, m\}$ and $k = m + 1$ separately. If $k \in \{1, \dots, m\}$, then $\min(kr, n) = kr$, since $r \leq m$ and $m = \lfloor n/r \rfloor$.

The set of positive integers $j$ satisfying $(k-1)r < j \le kr$ is $\{\lfloor(k-1)r\rfloor + 1, \lfloor(k-1)r\rfloor + 2, \dots, \lfloor kr\rfloor\}$. Hence,
$$s_k = \lfloor rk \rfloor - (\lfloor r(k-1) \rfloor + 1) + 1 = \lfloor rk \rfloor - \lfloor r(k-1) \rfloor$$
for all $k \in \{1, \dots, m\}$. If $k = m + 1$, then $(k-1)r < j \le \min(kr, n) = n$. The set of positive integers $j$ satisfying $(k-1)r < j \le kr$ is $\{\lfloor(k-1)r\rfloor + 1, \dots, n\}$. Then $s_{m+1} = n - \lfloor r(k-1) \rfloor = n - \lfloor mr \rfloor$. Note that this number is non-negative by the definition of $m$. Therefore, by the definition of $s_k$, we have
$$\begin{aligned} \sum_{j=1}^{n} \min \left( \left\lfloor \frac{j}{r} \right\rfloor, n \right) &= \sum_{k=1}^{m+1} k s_k \\ &= \sum_{k=1}^{m} \left( k \left( \lfloor kr \rfloor - \lfloor (k-1)r \rfloor \right) \right) + (m+1)(n - \lfloor rm \rfloor) = (m+1)n - \sum_{k=1}^{m} \lfloor kr \rfloor. \quad (4) \end{aligned}$$
Summing (??) and (??) yields that
$$g(r) = n^2 + n + \sum_{j=1}^{m} (\lceil jr \rceil - \lfloor jr \rfloor) \ge n^2 + n,$$
which proves the right inequality. $\square$