You are seeking polyhedra that realize genus-$g$ surfaces and have the fewest convex faces. A related goal has seen considerable work: the same problem but minimizing the number of vertices, so-called vertex-minimal triangulations. For example, this paper finds all the $g=3$ and $g=4$ vertex-minimal triangulations, and finds a $12$-vertex $g=5$ example:

Hougardy, Stefan, Frank H. Lutz, and Mariano Zelke. "Surface realization with the intersection segment functional." Experimental Mathematics 19.1 (2010): 79-92. (arXiv abs.)

This work has subsequently been extended: Brehm, Ulrich, and Undine Leopold. "Polyhedral Embeddings and Immersions of Many Triangulated 2-Manifolds with Few Vertices." arXiv:1603.04877 (2016). (arXiv abs.)

I interpret your question as seeking polyhedra that realize genus-$g$ surfaces and have the fewest number of convex faces. A related goal has seen considerable work: the same problem but minimizing the number of vertices, so-called vertex-minimal triangulations. For example, this paper finds all the $g=3$ and $g=4$ vertex-minimal triangulations, and finds a $12$-vertex $g=5$ example:

Hougardy, Stefan, Frank H. Lutz, and Mariano Zelke. "Surface realization with the intersection segment functional." Experimental Mathematics 19.1 (2010): 79-92. (arXiv abs.)

This work has subsequently been extended: Brehm, Ulrich, and Undine Leopold. "Polyhedral Embeddings and Immersions of Many Triangulated 2-Manifolds with Few Vertices." arXiv:1603.04877 (2016). (arXiv abs.)