Did you guys look at bare metal at all? (either dedicated or colocated)? Spot gets you in the same ballpark of price on a "unit", which can be mentally deceiving since an AWS unit is pretty weak.
In our experience with CPU or IO intensive workloads, Spots are still 2-5x slower than what you can get at decent dedicated provider..