If you make the assumption that there is a relatively smooth function underlying the grid of parameters, then there are certain things that you can do. For example, one simple heuristic is to start with a very coarse grid of parameters, and then use a finer grid around the best of the parameter settings from the coarse grid.
This tends to work quite well in practice, with caveats of course. First is that the space is not necessarily smooth, and there could be local optima. The coarse grid may completely miss these and you could end up with a sub-optimal solution. Also note that if you have relatively few samples in your hold-out set, then you may have a lot of parameter settings that give the same score (error or whatever metric you're using). This can be particularly problematic if you are doing multi-class learning (e.g. using the one-versus-all method), and you have only a few examples from each class in your hold-out set. However, without resorting to nasty nonlinear optimisation techniques, this probably serves as a good starting point.
There's a nice set of references here. In the past I've taken the approach that you can reasonably estimate a good range of kernel hyperparameters by inspection of the kernel (e.g. in the case of the RBF kernel, ensuring that the histogram of the kernel values gives a good spread of values, rather than being skewed towards 0 or 1 - and you can do this automatically too without too much work), meaning that you can narrow down the range before starting. You can then focus your search on any other parameters such as the regularisation/capacity parameter. However of course this only works with precomputed kernels, although you could estimate this on a random subset of points if you didn't want to use precomputed kernels, and I think that approach would be fine too.