We study generic tests of strong-field General Relativity using gravitational waves emitted during the inspiral of compact binaries. Previous studies have considered simple extensions to the standard post-Newtonian waveforms that differ by a single term in the phase. Here we improve on these studies by (i) increasing the realism of injections and (ii) determining the optimal waveform families for detecting and characterizing such signals. We construct waveforms that deviate from those in General Relativity through a series of post-Newtonian terms, and find that these higher-order terms can affect our ability to test General Relativity, in some cases by making it easier to detect a deviation, and in some cases by making it more difficult. We find that simple single-phase post-Einsteinian waveforms are sufficient for detecting deviations from General Relativity, and there is little to be gained from using more complicated models with multiple phase terms. The results found here will help guide future attempts to test General Relativity with advanced ground-based detectors.