I tried using an enhanced Tone library but wasn't able to introduce phase shift between the two PWMs
Instead, I'm writing directly to the registers (i.e. PORTD = B10000000;); I turn one on, pause, turn the second on, pause, turn the first off, pause, turn the second off, pause, repeat. however, the delayMicroseconds isn't precise enough because I need to be able to scale the frequencies from 25-75KHz with an interval of 0.2 kHz.
The best I've gotten so far as using in-line assembly to call a bunch of "nop"s and stall that way... this is obviously far from ideal, however.
So two questions:
Is this high frequency, phase shifted, square-wave output even possible on an Arduino or should I get a higher performance microcontroller?
And, if it's possible, how do I approach this problem?
When you use an timer interrupt, you'll need 4 interrupts per cycle, to turn the signals on and off.
The difference between 75kHz ~ 13.33µs and 74.8 kHz ~ 13.37µs is 40ns, or 10ns for 4 interrupts, i.e. 100MHz timer frequency. This is far beyond the clock frequency of an Arduino 
And the interrupt handler must increment a variable and check which port pin to change, in addition to the general interrupt overhead, so that a clock frequency of several GHz would be more appropriate. Polling for counter overflows could be used instead of interrupts, with slightly better performance.
A single NOP instruction will take 40ns @ 20MHz, plus output pin changes about 100ns, still away by a factor of 10 from your intended frequency granularity. And this is the best case, with dedicated loops for every single frequency! Using a loop for the delay will make it much slower.
So I'd say no, you'll already have problems with finding an controller (DSP?) that operates at the required speed.
Provided that you can find a digital counter IC, operating at 100MHz and with synchronous preload, you can try to add two flip-flops for the signal generation, and a register to preload the counter to the desired number of ticks for the intended frequency, on every counter overflow. For the minimum output frequency a divisor of 100M/25k=4k is required, i.e. the counter and register must have 12 bits at least. Then the Arduino can compute the required number of ticks and load it into the register. Eventually the Arduino can create the output signals from the counter overflows, saving the two flip-flops. When you reduce the granularity at the maximum frequency, the required clock frequency will decrease by just that factor.
Please check my calculations, I'm not a computer 
Actually, it turns out I was able to get a decent resolution (about 0.7 kHz) using the following code:
//set port B to output
DDRB |= 0xFF;
// wgm mode 1110 (fast pwm w/ TOP = ICR1
TCCR1A |= 1<<WGM11 ;
TCCR1B |= 1<<WGM12 | 1<<WGM13;
//set OC1/A and OC1B on compare match w/ ICR1 , clear them at bottom
TCCR1A |= 1<<COM1A1 | 1<<COM1A0| ;
TCCR1A |= 1<<COM1B1 | 1<<COM1B0 ;
//pre-scaler = 1
TCCR1B |= 1<<CS10;
ICR1 = 16000000/freq; // input compare value = (clock freq) / (desired freq)
// 50% duty cycle on OCR1A/B
OCR1A = ICR1/2;
OCR1B = ICR1/2;
Now I just need to figure out how to introduce a delay of period/4 between OC1A and OC1B... Any thoughts?
I tried writing the line -- TCNT1 = 1/freq/4; -- in between the last and second to last lines (OCR1A=... and OCR1B =...)
Thanks again!