We present fast frequency- and time-domain spectrally accurate solvers for Partial Differential Equations that address some of the main difficulties associated with simulation of realistic engineering systems. Based on a novel Fourier-Continuation (FC) method for the resolution of the Gibbs phenomenon and fast high-order methods for evaluation of integral operators, these methodologies give rise to fast and highly accurate frequency- and time-domain solvers for PDEs on general three-dimensional spatial domains. Our fast integral algorithms can solve, with high-order accuracy, problems of electromagnetic and acoustic scattering for complex three-dimensional geometries; our FC-based differential solvers for time-dependent PDEs, in turn, give rise to essentially spectral time evolution, free of pollution or dispersion errors, for general PDEs. A variety of applications to linear and nonlinear PDE problems demonstrate the significant improvements the new algorithms provide over the accuracy and speed resulting from other approaches.