I don't know an easy way to bound the genus from below (and I would love to hear of one), but there is a fairly general automated technique that can be used to simplify affine curves given by a plane equation (one that is not necessarily irreducible and possibly has many singularities).  If the genus of the curve is small, the equation can often be simplified dramatically (possibly made trivial if the genus is 0).  On the other hand, if the algorithm fails to make any progress you really can't say anything (so no lower bound).

The basic idea is as follows.  First define a cost metric that measures the "complexity" of a given plane equation that defines your curve (e.g. in terms of the degree in each variable, number of nonzero terms, coefficient sizes, etc...).  Now define a small set of atomic "steps", say $d$ of them, each of which corresponds to a simple birational transformation (e.g. $x \to 1/x$ might be one step).

Now consider the (infinite) $d$-regular graph whose edges correspond to atomic steps and whose vertices consist of birationally equivalent curves.  We want to find a path from the given curve to one with lower cost.  This is a combinatorial optimization problem that can be tackled with standard local search techniques (e.g. hill-climbing, simulated annealing, etc...).  It isn't guaranteed to work (you could get stuck at a bad local minima), but it can be quite effective.

This technique was originally developed in an effort to find "good" defining equations for $X_1(N)$ (which came up in another [Math Overflow question][1]) but it applies to any plane curve, see Section 3 of [http://arxiv.org/abs/0811.0296][2] for more details.

  [1]: https://mathoverflow.net/questions/14054/where-can-i-find-a-comprehensive-list-of-equations-for-small-genus-modular-curves/18812#18812
  [2]: http://arxiv.org/abs/0811.0296