Plane wave pseudopotential methods are used to investigate the structures and total energies of AlOOH and FeOOH in the five canonical oxyhydroxide structures: diaspore (goethite), boehmite (lepidocrocite), akaganeite, guyanaite, and grimaldiite. The local density approximation was used in conjunction with ultrasoft pseudopotentials in full optimizations of both AlOOH and FeOOH in each of these structures. Structures are in reasonably good agreement with experiment, with lattice parameters and bond lengths within 3% of experimental values. Neither AlOOH nor FeOOH have been identified in the grimaldiite or guyanaite structures, however we find that total energies for AlOOH and FeOOH in these structures are comparable to or lower than the total energies of the commonly observed polymorphs (with the exception of FeOOH in the grimaldiite structure, which is anomalously high energy). Estimated zero-point energy corrections do not alter this result. For diaspore and boehmite, we also provide calculations using the generalized gradient approximation and norm-conserving pseudopotentials to assess the extent to which the results depend on the particular level of theory used. We find that diaspore is predicted to have a lower energy, consistent with experimental observation, using all but one methodological combination where the generalized gradient approximation is combined with ultrasoft pseudopotentials. Thus, although one may reasonably conclude that the differences in total energies of the various (Al,Fe)oxyhydroxide polymorphs are small, current electronic structure methods do not appear to be fully capable of accurately resolving these small differences. These findings provide further confirmation that the structures of oxyhydroxide polymorphs and surface precipitates are more likely to be a function of kinetics than of intrinsic lattice stability.