The standard method to study the diffusion of a particle in a system with immobile obstacles is to use Monte Carlo simulations on finite-size lattices with periodic boundary conditions. For example, the diffusion of proteins on the surface of biomembranes in the presence of fractal and random aggregates of obstacles has been studied extensively by M. J. Saxton. In this article, we derive two algebraically exact methods to calculate the diffusion coefficient D for such systems. The first method reduces the problem to that of a first passage problem. The second one uses the Nernst-Einstein relation to transform the problem into a field-driven drift problem where D is related to the zero-field mobility. Systems with closed volumes and multiple independent pathways are discussed. In the second part [Mercier and Slater, J. Chem. Phys. 110, 6057 (1999), following paper], a numerical implementation will be described and tested, and several examples of applications will be given.