We study the existence of traveling breathers and solitary waves in the discrete p-Schrödinger (DpS) equation. This model consists of a one-dimensional discrete nonlinear Schrödinger equation with strongly nonlinear inter-site coupling (a discrete p-Laplacian). The DpS equation describes the slow modulation in time of small amplitude oscillations in different types of nonlinear lattices, where linear oscillators are coupled to nearest-neighbors by strong nonlinearities. Such systems include granular chains made of discrete elements interacting through a Hertzian potential (p = 5/2 for contacting spheres), with additional local potentials or resonators inducing local oscillations. We formally derive three amplitude PDE from the DpS equation when the exponent of nonlinearity is close to (and above) unity, i.e. for p lying slightly above 2. Each model admits localized solutions approximating traveling breather solutions of the DpS equation. One model is the logarithmic nonlinear Schrödinger (NLS) equation which admits Gaussian solutions, and the other are fully nonlinear degenerate NLS equations with compacton solutions. We compare these analytical approximations to traveling breather solutions computed numerically by an iterative method, and check the convergence of the approximations when p → 2 +. An extensive numerical exploration of traveling breather profiles for p = 5/2 suggests that these solutions are generally superposed on small amplitude nonvanishing oscillatory tails, except for particular parameter values where they become close to strictly localized solitary waves. In a vibroimpact limit where the parameter p becomes large, we compute an analytical approximation of solitary wave solutions of the DpS equation.