Let's say we have 2 classes (-1 and 1), 1 feature (x), and an arbitrary amount of data points. Why can't we always find a frequency and phase that fit a sine wave or a square wave to our data points? When graphed, as frequency is increased, the sine function almost seems to cover the entire [-1≤y≤1] domain, so it isn't intuitive why we can't always find a periodic function that fits our data perfectly. Is there a way to prove that not all data is periodic?
In order for data to be periodic, there needs to be a "time" independent variable over which the data depends. Not always there is a time variable in the data so, in those cases, you cannot approximate the data with trigonometric functions.
For the cases where there is time in the data, you can use the Discrete Sine Transform, as well as the more popular Discrete Cosine Transform, to approximate the signal in terms of a sum of sine/cosine functions oscillating at different frequencies. You should take into account, however, that discontinuities affect the DCT accuracy; from the wikipedia page for the DCT:
In particular, it is well known that any discontinuities in a function reduce the rate of convergence of the Fourier series, so that more sinusoids are needed to represent the function with a given accuracy. The same principle governs the usefulness of the DFT and other transforms for signal compression; the smoother a function is, the fewer terms in its DFT or DCT are required to represent it accurately, and the more it can be compressed.