I agree that both grads and polarizers have the potential to look fake. A lot of people overuse polarizers, just because they are more common. I lean toward grads.
Remember that with a very wide lens, you can't evenly polarize the whole field, so usually it's best to avoid a polarizer in such cases, unless the composition lends itself to selective polarization and it can be done so it looks natural. I might occasionally use a polarizer with a 50mm lens on 6x6, for instance, but never with a 40mm lens.