A computational approach is presented to compute anharmonic vibrational states of solids from quantum-mechanical DFT calculations by taking into explicit account phonon-phonon couplings via the vibrational configuration interaction (VCI) method. The Born-Oppenheimer potential energy surface (PES) is expanded in a Taylor's series in terms of harmonic normal coordinates, centered at the equilibrium nuclear configuration, is truncated to quartic order, and contains one-mode, two-mode, and three-mode interatomic force constants. The description of the anharmonic terms of the PES involves the numerical evaluation of high-order energy derivatives (cubic and quartic in our case) with respect to nuclear displacements and constitutes the most computationally demanding step in the characterization of anharmonic vibrational states of materials. Part I is devoted to the description of the PES. Four different numerical approaches are presented for the description of the potential, all based on a grid representation of the PES in the basis of the normal coordinates, that require different ingredients (energy and/or forces) to be evaluated at each point (i.e., nuclear configuration) of the grid. The numerical stability and relative computational efficiency of the various schemes for the description of the PES are discussed on two molecular systems (water and methane) and two extended solids (Ice-XI and MgH2). All the presented algorithms are implemented into a developmental version of the Crystal program.