Let's assume that $N$ divides $800 \times 800 = 64000$ for now. Then in order to split up the $800 \times 800$ image we factorise $N$ into integers $(a, b)$ such that $a|800$ and $b|800$.
For example, if $N = 10$ then you have $(1, 10)$, $(2, 5)$, $(5, 2)$ and $(10, 1)$ as valid factorisations. Then each rectangular slice would have dimensions $\frac{800}{a} \times \frac{800}{b}$. So for $N = 10$ the solutions are:
$\frac{800}{1} \times \frac{800}{10} = 800 \times 80$
$\frac{800}{2} \times \frac{800}{5} = 400 \times 160$
$\frac{800}{5} \times \frac{800}{2} = 160 \times 400$
$\frac{800}{10} \times \frac{800}{1} = 80 \times 800$
Note that for some $N$, there may be. For example, $(1600, 1)$ is not a valid factorisation for $N = 1600$ because 1600 exceeds the side lengths of the initial $800 \times 800$ image.
If $N$ does not divide 64000 then you cannot divide the image into equal rectangles.
Let us call $w$ and $h$ the width and height of the rectangle. If we start by considering perfectly square cells of size $s \times s$, the maximal area that can be covered is given by the product between the maximal number of packable cells $\displaystyle \lfloor{\frac{w}{s}}\rfloor \cdot \lfloor{ \frac{h}{s}}\rfloor$ and the area $s^2$ of each cell. It is not difficult to show that the remaining uncovered area R is given by
$$ R =h \cdot [w\pmod s]+ w \cdot [h \pmod s] - [w \pmod s] \cdot [h \pmod s] $$
For example, covering a $200 \times 50$ rectangle with area $A=10000$ using $7 \times 7$ cells, the maximal number of cells is $\displaystyle \lfloor{\frac{200}{7}}\rfloor \cdot \lfloor{ \frac{50}{7}}\rfloor=28 \cdot 7=196$, and the maximal covered area is $196 \cdot 7^2=9604$. The remaining uncovered area, which in this example is $10000-9604=396$, corresponds to
$$R= 50 \cdot [200\pmod 7]+ 200 \cdot [50 \pmod 7] - [200 \pmod 7] \cdot [50 \pmod 7]\\ =50 \cdot 4+ 200 \cdot 1- 4 \cdot 1=396$$
The formula for $R$ showed above, which for $s$ equal to max(cellMinWidth, cellMinHeight) also reflects the residual uncovered area obtained by applying the solution proposed in the OP, explains why this approach works well when $w$ and $h$ are similar, and fails when the difference between $w$ and $h$ is big. In fact, noting that both mod terms can range between $0$ and $s$, we get that the value of $R$ ranges between $0$ and $s(w+h-s)$. So, for a rectangle with given area $A=w \cdot h$ to be covered with cells of size $s \times s$, the condition that minimizes the sum $w+h$ (and that therefore minimizes the upper bound of $R$) clearly corresponds to the case $w=h$ (this is easily checked by setting $h=A/w$ and noting that $w+h=w+A/w$ has a minimum in $w=\sqrt{A}$). Accordingly, if we vary $w$ and $h$ by keeping their product constant (i.e., if we consider rectangles with constant area and variable proportions), the sum $w+h$ and the upper bound of $R$ progressively increases as the rectangle proportion departs from $1$ and as the difference between $w$ and $h$ becomes larger. This is also visible starting from the same example of a $200 \times 50$ rectangle as above: covering it with $s \times s$ cells, the value of $R$ ranges between $0$ and $s(250-s)$, but the upper bound of $R$ decreases to $s(200-s)$ if we consider a $100 \times 100$ rectangle, and raises to $s(1010-s)$ if we consider a $1000 \times 10$ rectangle (in both cases, despite no changes in the rectangle area). This explains why this method leads to a high probability of having a large uncovered area when the difference between $w$ and $h$ is large.
These considerations suggest that, when choosing the value of cell side $s$ to divide a $w \times h$ rectangle in the "best" way, a good idea could be to test all possible values of $s$, starting from the minimal values allowed, and to choose the value that minimizes $R$ according to the formula above. This analysis can be easily and rapidly obtained by a simple algorithm on a PC. Once the value of $s$ that minimizes $R$ has been found, we can also make a minimal variation in the cell size to achieve a $100\%$ covering, by adding to the cell width and height (until now considered equal in our analysis) a small quantity obtained by dividing the residual uncovered edges among all cells. The formulas for these small final adjustments are $\displaystyle \frac{w \pmod s}{\lfloor {w/s} \rfloor}$ and $\displaystyle \frac{h \pmod s}{\lfloor {h/s} \rfloor}$. For instance, if we find that in a $90 \times 34$ rectangle the best value for $s$ is $11$, we can initially cover the rectangle with a $8 \times 3$ grid of square cells of size $11$. Then, we can take the remaining edges $90 \pmod {11}=2$ and $34 \pmod {11}=1$ and distribute them among all cells, obtaining a $100\%$ covering using cells with width $11 +\frac{2}{8}=11.25$ and height $11+\frac{1}{3}\approx 11.33$. This keeps a nearly square shape for the cells and allows a complete covering.
Lastly, if we want to find a more rapid method to choose a good value of $s$ that avoids the need of testing all its possible values, it could be more convenient to privilege minimization of the mod term that, in the formula for $R$, is multiplied by the longest dimension of the rectangle. Taking again the same example of a $200 \times 50$ rectangle, to divide it in cells of size $s$ it is convenient to choose a value of $s$ that makes $50\pmod s$ as small as possible (privileging this, rather than minimization of $200\pmod s$), since then this mod term has to be multiplied by $200$. Although this method does not guarantee that the best value of $s$ is found, it might be useful to create simplified, faster algorithms to find "good" values of $s$.
Best Answer
Here is the full solution. The answer is, indeed, $5/2$. An example was already presented by the OP. Now we need to prove the inequality.
First of all we notice that for any color (blue or yellow) the sum of height/width (or width/height) ratios is always at least $1/2$.
Indeed, since all dimensions do not exceed $1$, we have (e.g., for blue color) $$ \sum \frac{w_i}{h_i} \geqslant \sum w_i h_i = \frac 12 \,. $$ as the final sum is the total area of all blue rectangles.
Second, we observe that either the blue rectangles connect the left and the right sides of the square, or the yellow rectangles connect the top and the bottom sides. We leave that as an exercise for the readers :) (Actually, as you will see below, it would suffice to show that either the sum of all blue widths or the sum of all yellow heights is at least $1$.)
Without loss of generality, assume that the blue rectangles connect the lateral sides of the large square. Then we intend to prove that $$ \sum \frac{w_i}{h_i} \geqslant 2 \,, $$ where the summation is done over the blue squares. Combining that with the inequality $\sum h_i/w_i \geqslant 1/2$ for the yellow squares we will have the required result, namely that the overall sum is always at least $5/2$.
Since the projections of the blue squares onto the bottom side must cover it completely, we have $\sum w_i \geqslant 1$. We also have $\sum w_ih_i = 1/2$. Now all we need is the following fact.
Lemma. Two finite sequences of positive numbers $\{w_i\}$ and $\{h_i\}$, i = $1$, ... , $n$ are such that $$ \sum w_i = W, \qquad \sum w_ih_i = S \,. $$ Then $$ \sum \frac{w_i}{h_i} \geqslant \frac{W^2}S \,. $$
Proof. We will use the well-known Jensen's inequality (which follows from the geometric convexity of the area above the graph of any convex function) for function $f(x) = 1/x$. That gives us $$ \sum \frac{w_i}W f(h_i) \geqslant f \left( \sum \frac{w_i}W h_i \right) \,. $$ In other words $$ \frac1W \sum \frac{w_i}{h_i} \geqslant \frac1{\sum \frac{w_i}W h_i } = \frac{W}{\sum w_i h_i} = \frac WS \,. $$ and the required inequality immediately follows. $\square$
Applying this lemma to our case where $W \geqslant 1$ and $S = 1/2$ completes our solution.