Well, this particular strategy generalizes for finding the k best horses when the track size is $n = (k-1)(k+2)/2$ and the number of horses is $n^2$, and it takes n+2 races as in your example:
Split them into n groups of size n, race them in those sets, and label as $a_{11}, a_{12}, \dots, a_{1n}, a_{21}, a_{22}, \dots, a_{2n}, \dots, a_{nn}$ as before (so the horse who came in $j$th place in the $i$th race has label $a_{ij}$. Then race $a_{11}, a_{21},\dots,a_{n1}$, and relabel the first subscripts of all horses using the results of this race. The winner of that race is the best horse. To determine the other k-1 best horses, race the n other horses who have fewer than k horses that are better than them (directly or by transitivity): $a_{12}, a_{13}, \dots, a_{1k}, a_{21}, a_{22}, \dots, a_{2(k-1)}, a_{31}, a_{32}, \dots, a_{3(k-2)},\dots, a_{k1}$. (Note here that conveniently $n = (k-1) + (k-1) + (k-2) + (k-3) + \dots + 2 + 1 = (k-1)(k+2)/2$.)
But this still leaves open the question of what to do for other cases.
JHI's elegant lower bound of $8$ on $N$ is achieved by an explicit dissection.
I show my construction below; you might want to try to find
a solution yourself before proceeding $-$ it makes for a neat puzzle.
There may well be other ways to do it.
If somebody can make a "$3$-dimensional" graphic or picture of the
$8$-piece dissection, you're welcome to add it by editing my answer.
My diagrams are two-dimensional, labeling each piece with its height.
Fortunately the dissection is simple enough for this to be possible;
in particular, the eight pieces comprise four boxes and four L-shaped prisms.
This also made it possible to find the solution using just pencil and paper
on an otherwise uneventful international flight.
Begin by cutting the $6 \times 6 \times 6$ cube top to bottom
into three pieces, as shown in top view in the first square diagram.
Then cut each piece horizontally in two, dividing AB into $3+3$,$\phantom.$
C into $4+2$, and D into $5+1$. Each AB piece is then further subdivided
into a box B and an L-shaped prism A. The second diagram shows (say) the
bottom layer of four pieces, and the third diagram shows the top.
Note that the AB subdivisions are not quite the same.
(source)
Pieces with the same color will come together to form a smaller cube.
The larger C piece is a $4$-cube,
and the two A pieces form a $3$-cube as shown.
It remains to construct the $5$-cube from the remaining five pieces.
The last two diagrams show the bottom and top of the $5$-cube.
(source)
The two $5$'s are the larger B piece, rotated to span the entire
height of the cube, and the thick D piece.
The thin D piece completes the bottom, with width $1$.
The top is filled by the thinner C piece and the smaller B,
both rotated to height 4. QEF
I guess that a physical model won't make for a hard puzzle to reconstitute
into either one or three cubes (e.g. the AB, C, and D parts of the $6$-cube
are independent) but would still make a nice physical model of the identity
$3^3 + 4^3 + 5^3 = 6^3$.
This dissection is specific to the solution $(a,b,c;d)=(3,4,5;6)$ of the
Diophantine equation $a^3+b^3+c^3=d^3$; I don't know whether an $8$-piece
dissection is possible for any other solution. JHI's analysis shows that
one can never get below $8$, and in some cases even that's not possible:
if $a<b<c$ and $a+c<d$ then there's at least one corner of the $d$-cube,
say $(1,1,1)$, that contributes to the $a$-cube, but then any cell
$(x,y,z)$ with $\max(x,y,z) = a+1$ cannot connect to any corner.
This first happens for $(a,b,c;d) = (6,32,33;41)$.
What's the minimal dissection for the "taxicab" identity
$1^3 + 12^3 = 9^3 + 10^3$? JHI's corner-cutting argument shows
that at least nine pieces are needed.
Best Answer
This is a variation on a classic card trick (audience pick 5 cards, magician A removes a card of his choosing and hands the rest to magician B, who then names the missing card.)
There are two ways you can view the process - from the point of view of the cube-orienter, or from the point of view of the final guesser.
It turns out to be more useful to consider the cube-orienter's job.
Given a cube, he has to pick an orientation to leave it in. Let's view this as a function from the set of possible cubes to the set of 'visible orientations', i.e. we ignore what's on the bottom face. Then this function must be a bijection, and it must satisfy the constraint that the image of a cube under this function does give a valid 'visible orientation' of that cube.
This constraint can be represented as a bipartite graph, where there are $\frac{1}{24}n(n-1)(n-2)(n-3)(n-4)(n-5) = 30\binom{n}{6}$ vertices on the left representing the different cubes, $n(n-1)(n-2)(n-3)(n-4)$ vertices on the right representing the 'visible orientations', and each cube has $24$ edges linking it to its valid 'visible orientations'. Conversely, each 'visible orientation' has $n-5$ edges linking back to the cubes it could have arisen from. In this context, the bijective function we seek is a matching in this graph.
Hence the original problem is equivalent to the existence of a matching in this bipartite graph. A necessary and sufficient condition for such a matching to exist is given by Hall's Marriage Theorem. We need to check that for any set of $k$ cubes, the cardinality of the union of 'visible orientations' linked to these cubes is greater than or equal to $k$. But $k$ cubes give rise to $24k$ edges, which give rise to at least $24k/(n-5)$ 'visible orientations', which is greater than or equal to $k$ for $n \leq 29$.
So there is a strategy for $n = 29$, and conversely this is the best possible just by comparing the number of vertices on either side.
Update: An explicit strategy was requested, so here is an adaptation of the standard card trick strategy:
Let's assume we're working with numbers from $0$ to $28$ for convenience.
The cube-orienter adds up the numbers on all the faces of the cube modulo $6$. Call the result $i$, with $0 \leq i \leq 5$. Now if $i=0$, put the smallest face face-down, if $i=1$, put the second smallest face-down, and so on. Later on, the guesser will be able to add up all the visible faces modulo $6$, and a little thought shows that the hidden face will be congruent to the negative of this modulo $6$, provided the guesser renumbers the unseen numbers from $0$ to $23$. This means the guesser will know the answer is one of $4$ cards, and these remaining $4$ degrees of freedom can be communicated by the $4$ possible rotations the cube-orienter can leave the cube in (with a fixed face down). E.g. of the side-faces, the largest can be pointing left/forward/right/backward.