1) What is the difference between SMO (weka) and the LibSVM algorithms? Which is the best? Because the parameter requirements of the two are very different.
SVM is a classifier algorithm problem, SMO is one of the common optimization algorithms to solve this problem, libSVM is a library implements SMO.
2) Feature reduction (e.g.PCA) and feature selection (e.g. InfoGain) are two different techniques for reducing features. Which one to rely on? In which conditions are they to be used?
Feature reduction makes feature transformation, while feature selection doesn't
3) In Infogain eval, the ranking algorithm ranks the features and the threshold parameter can remove the unwanted features with respect to entropy measure. Can we optimize both? Or do we optimize one of them alternatively? What I should I be looking for - accuracy?
This question is not clear, what does both stand for? Entropy and what? Optimization methods are very flexible, you can change the optimization target function if you want.
4) Is accuracy the only thing that I should be looking for? Of course there is overfitting, but can I quantify the predictive power of the model other than just CV accuracy? Some other measure or technique?
Accuracy is not the only concern. You should do careful validation (use techniques like K-fold cross validation) to test the generalization ability of your model. And be noted, for same accuracy, the fewer features you use, the better your model is.