How big should my case be?

I overclock my CPU and GPU about 15-20% and have a 550w PSU... 800w would only be needed if you are planning on going SLI.

Anyway, to your question. Any ATX mid/full tower will do you fine. You just want to make sure it has a spot for a 240mm radiator. If it has 2 120mm fan mounts side-by-side, that'll work as well. Also want to look for a case with at least 11" of GPU clearance.