The only other big trick is to use a high-flow solenoid valve; we are using McMaster part number 6124K511 to feed each of our pistons. The valves you get from AndyMark or Vexpro flow about 3x less air (these were the maximum flow rate that we could use in the past... this year's rule set has allowed us to use a much larger variety of solenoids).
The geometry of the arm also plays a big role. Based on the videos you posted, I would extend the length of the platform that is shooting the ball, and move the piston locations on the base mounting board back about 0.5"-1" from the pivot location to allow it to sit "flatter" before firing. These pivot locations will all probably need a bit of adjustment as you continue testing.
Oh, and if you can get rid of the miles and miles of tubing between your pneumatics testing board and the catapult, you will probably see an immediate improvement.
EDIT: as far as gravity returning the catapult arm to the starting position, we have never had any trouble with this. It falls right back into place with ease.