Why it's impossible:
There are actually 4 more arithmetic sequences that will always be present in a magic square.
Let the square:
$$a,b,c$$
$$d,e,f$$
$$g,h,i$$
So from $(3)$ and $e=\frac{r}{3}$ we get the equations:
$$a-e=e-i$$
$$b-e=e-h$$
$$c-e=e-g$$
$$d-e=e-f$$
$(6)$ From these we get:
$$2e=a+i=b+h=c+g=d+f$$
Next take:
$$r=a+b+c=a+d+g\implies b+c=d+g$$
Then from $(6)$, substitute in $g=b+h-c$ to get:
$$b+c=d+(b+h-c)$$
Rearrange:
$$d-c=c-h$$
The same "trick" can be done too for $(b,g,f),(b,i,d),(h,a,f)$ either using the same method or the symmetries of the magic square.
$(7)$ We have:
$$d-i=i-b$$
$$b-g=g-f$$
$$f-a=a-h$$
$$h-c=c-d$$
Note the middle elements are the corners, which is helpful for remembering these.
Back to your question now.
For $r=15$ we have 4 sequences across the center: $(1,9),(2,8),(3,7),(4,6)$
From these we can make 5 more arithmetic sequences: $(1,2,3),(2,4,6),(1,4,7),(3,6,9),(7,8,9)$
All 5 progressions have at least one even number so no such square is possible!
Finding the smallest odd magic square:
Since the square with $5$ in the center (and a total of $15$) is impossible. Let's try the square with $7$ in the center.
The sequences about 7 are $(1,13),(3,11),(5,9)$
From these we can pull the sequences $(1,3,5),(1,5,9),(9,11,13),(5,9,13)$
The middle elements will become the centers and the left/right elements will become the middles of the edges of the square. This implies $5$ and $9$ will be duplicated. So no distinct square exists with center element $e=7$
However for $e=9$ we can take the pairs about $9$: $(1,17),(3,15),(5,13),(7,11)$
Now note for the equations in $(7)$, each equation's last variable is the first variable of the equation following it. That is to say, we must pull 4 sequences from the elements of the pairs above such that they form a sort of loop with their first and last elements. The right sequence can be found with a small bit of work:
$$\rightarrow(1,7,13)\rightarrow(13,15,17)\rightarrow(17,11,5)\rightarrow(5,3,1)\rightarrow$$
Now we construct the square, starting with $(1,7,13)$:
$$a,[1],c$$
$$[13],[9],f$$
$$g,h,[7]$$
Then $(13,15,17)$:
$$a,1,[15]$$
$$[13],9,f$$
$$g,[17],7$$
Then $(17,11,5)$:
$$[11],1,15$$
$$13,9,[5]$$
$$g,[17],7$$
Finally $(5,3,1)$:
$$11,[1],15$$
$$13,9,[5]$$
$$[3],17,7$$
And we're done. The smallest all odd magic square has $r=27$
$$11,1,15$$
$$13,9,5$$
$$3,17,7$$
I don't know about the 4x4 case, but here are some things we can do for the 5x5 case.
Start with a typical 5x5 magic square (sum = 65):
\begin{array}{|c|c|c|c|c|}
\hline
17 & 24 & 1 & 8 & 15\\
\hline
23 & 5 & 7 & 14 & 16 \\
\hline
4 & 6 & 13 & 20 & 22 \\
\hline
10 & 12 & 19 & 21 & 3 \\
\hline
11 & 18 & 25 & 2 & 9 \\ \hline
\end{array}
Multiply all entries by 2 (sum = 130):
\begin{array}{|c|c|c|c|c|}
\hline
34 & 48 & 2 & 16 & 30\\
\hline
46 & 10 & 14 & 28 & 32 \\
\hline
8 & 12 & 26 & 40 & 44 \\
\hline
20 & 24 & 38 & 42 & 6 \\
\hline
22 & 36 & 50 & 4 & 18 \\ \hline
\end{array}
Add 1 to selected cells (sum = 131)
\begin{array}{|c|c|c|c|c|}
\hline
34 & \color{red}{49} & 2 & 16 & 30\\
\hline
\color{red}{47} & 10 & 14 & 28 & 32 \\
\hline
8 & 12 & \color{red}{27} & 40 & 44 \\
\hline
20 & 24 & 38 & 42 & \color{red}{7} \\
\hline
22 & 36 & 50 & \color{red}{5} & 18 \\ \hline
\end{array}
OK, so this immediately shows that the sum need not be a multiple of n.
Obviously, I could have added 3 to those cells as well, so then the sum would be 133. I can't add 2, for then I would get duplicate entries. However, I can get a sum of 132 by adding 67 to these 5 cells in the original square. In fact, I could just stick to the original square and add any number greater than 25 to those 5 cells to get any sum of 90 or more. And by picking those 5 cells a little more carefully (or by choosing a different original 5x5 square), we can go even lower than that, though 65 is of course the minimum ... if we stick to positive numbers.
Assuming we are allowed to use negative numbers though, I can get any sum I want, since if the number I want is a multiple of 5, then add or subtract the appropriate number to each cell of the original magic square, and if what I want is not a multiple of 5, then multiply all entries by 5, and add or subtract the appropriate number to the 5 selected cells as we did above (we multiplied by 5 so as to ensure that we don't get duplicate entries when we add or subtract the number which is not a multiple of 5). E.g:
Wanted: sum = 10. OK, then take original square and subtract 11 from each entry:
\begin{array}{|c|c|c|c|c|}
\hline
6 & 13 & -10 & -3 & 4\\
\hline
12 & -6 & -4 & 3 & 5 \\
\hline
-7 & -5 & 2 & 9 & 11 \\
\hline
-1 & 1 & 8 & 10 & -8 \\
\hline
0 & 7 & 14 & -9 & -2 \\ \hline
\end{array}
Wanted: sum = 1. OK, then multiply all entries by 5 (sum = 325), and subtract 324 from the 5 selected cells:
\begin{array}{|c|c|c|c|c|}
\hline
85 & -204 & 5 & 40 & 75\\
\hline
-209 & 25 & 35 & 70 & 80 \\
\hline
20 & 30 & -259 & 100 & 110 \\
\hline
50 & 60 & 85 & 105 & -309 \\
\hline
55 & 90 & 125 & -314 & 45 \\ \hline
\end{array}
OK, so this is just the 5x5 case, but it works for other n as well. For example, here is how you can pick 6 cells for a 6x6 to play with:
\begin{array}{|c|c|c|c|c|c|}
\hline
\color{red}{X} & X & X & X & X & X\\
\hline
X & X & X & X & \color{red}{X} & X\\
\hline
X & \color{red}{X} & X & X & X & X\\
\hline
X & X & X & X & X & \color{red}{X}\\
\hline
X & X & \color{red}{X} & X & X & X\\
\hline
X & X & X & \color{red}{X} & X & X\\
\hline
\end{array}
In fact, you can easily convince yourself that for any n>4 we can find these n cells for any nxn so that each row, column, and main diagonal has exactly one of those n cells.
Edit
OK, the 4x4 is also possible! (Thanks @RossMillikan !)
\begin{array}{|c|c|c|c|}
\hline
\color{red}{X} & X & X & X\\
\hline
X & X & \color{red}{X} & X\\
\hline
X & X & X & \color{red}{X}\\
\hline
X & \color{red}{X} & X & X\\
\hline
\end{array}
Best Answer
If every row in a matrix $A$ sums to $k$ then $k$ is an eigenvalue with eigenvector $v=[1,1,\ldots,1]^T$. Indeed, all the entries of the vector $Av$ are equal to $k$ trivially, so $Av=kv$.