This is the first of a pair of papers which address the problem of measuring the unredshifted power spectrum in optimal fashion from a survey of galaxies, with arbitrary geometry, for Gaussian or non-Gaussian fluctuations, in real or redshift space. In this first paper, that pair weighting is derived which formally minimizes the expected variance of the unredshifted power spectrum windowed over some arbitrary kernel. The inverse of the covariance matrix of minimum variance estimators of windowed power spectra is the Fisher information matrix, which plays a central role in establishing optimal estimators. Actually computing the minimum variance pair window and the Fisher matrix in a real survey still presents a formidable numerical problem, so here a perturbation series solution is developed. The properties of the Fisher matrix evaluated according to the approximate method suggested here are investigated in more detail in the second paper.