"stages" are a pretty generic term and they would be different depending on the vehicle. Basically stage one, two, three correspond to different power levels, each with their own drawbacks.
Firstly, a cold air intake is a good modification. Don't worry about puddles unless its one of those intakes that scoops air from under the bumper. I grew up in PA with cold air on most of my vehicles and its not an issue.
Most "chips" or tuners take advantage of improving the factory tune. Often times stage 1 will alter the fuel mixture. The factory usually tunes the wide-open fuel curve a little rich. This keeps NOx emissions down and prevents detonation in extreme situations. Since no smog test checks a vehicle at wide open throttle, they can lean a little bit of that fuel out of the program and free up a few HP. Stage two often adds an advanced spark curve which also adds a few more HP at the risk of needing premium fuel. Either way, tuners are not big power-per-dollar investments. They are very helpful for reprogramming the speedo for different tires or gear ratios, but as far as power... not usually a good ratio of dollars to power. Most of the improvements you feel will be in your head, not your butt.
An engine is a big air pump and as a side-effect they make power. Anything you can do to improve the quality (not necessarily quantity) of airflow will generate more power. Invest in a good cold air intake (or make one yourself with a trip to HomeDepot's plumbing section) and consider an aftermarket exhaust and headers. How much power they add will depend on how much of a restriction the factory pieces are.