Are there better alternative methods to choose C and Gamma which yield better training performance?
Grid search is slow as it spends a lot of time investigating hyper-parameter settings that are no where near optimal. A better solution is the Nelder-Mead simplex algorithm, which doesn't require calculation of gradient information and is straightforward to implement (there should be enough information on the Wikipedia page). There may also be some java code in the Weka toolbox, however I work in MATLAB and haven't looked at Weka in any great detail.
SMO is an algorithm for finding the model parameters, rather than the hyper-parameters.
The Nelder-Mead simplex method can involve as many function evaluations as a simple grid search. Usually the error surface is smooth enough close to the optimal parameter values that a coarse grid search followed by a finer one in a smaller region should suffice.
If you're interested in gradient based optimization of C and gamma, there are methods like optimizing the radius-margin bounds or optimizing the error rate on a validation set. The computation of the gradient of the objective function involves something like one SVM train but a simple gradient descent may involve only a few dozen iterations. (Look at http://olivier.chapelle.cc/ams/ for an article and a Matlab implementation.)
Here is an entry in Alex Smola's blog related to your question
Here is a quote:
[...] pick, say 1000 pairs (x,x’) at random from your dataset, compute the distance of all such pairs and take the median, the 0.1 and the 0.9 quantile. Now pick λ to be the inverse any of these three numbers. With a little bit of crossvalidation you will figure out which one of the three is best. In most cases you won’t need to search any further.