Orbital-density-dependent functionals, such as the Perdew-Zunger or the Koopmans-compliant functionals, are used to remove unphysical self-interaction energies and to restoremissing piece-wise linearity in approximate formulations of density-functional theory (DFT). At variance with functionals of the total density, orbital-density-dependent functionals are typically not invariant with respect to unitary transformations of the occupied states. Such additional degrees of freedom require an extension of established approaches for direct minimization that preserve their numerical robustness and efficiency, and make it possible to apply these advanced electronic-structure functionals to large or complex systems. In this work we adapt the ensemble-DFT algorithm [N. Marzari, D. Vanderbilt, and M. C. Payne, Phys. Rev. Lett. 79, 1337 (1997)] to the case of orbital-density-dependent functionals, partitioning the variational problem into a nested loop of (i) minimizations with respect to unitary transformations at a fixed orbital manifold, that lead to a projected, unitary-covariant functional of the orbitals only that enforces the Pederson condition and (ii) variational optimization of the orbital manifold for this projected functional. We discuss in detail both general and functional-dependent trends and suggest a procedure to efficiently exploit the combination of the different minimization strategies. The overall formulation allows for a stable, robust, and efficient algorithm, yielding great improvements over conventional techniques.