I downloaded an evaluation version of Mathematica, and FindFormula was able to find an exact solution to Sin(3 * Sin(x)) after around 30 seconds of computation. That probably explains why it's not available on Alpha -- way too computation intensive.
My concern now is that with anything more complicated, you can't tell if the calculation is making progress to a solution. There is also the function NonlinearModelFit which requires a structured parametric model and also works with the same limitations.
So the benefit of Eureqa is that it will provide a continuous updating of the solution, allowing one to evaluate progress. And the Excel Solver also has a continual updating of the objective function value, at any which point in time the computation can be terminated.