I'm a nationally certified personal trainer. I'm also a kinesiology major for sports care and physical therapy, so here are my two cents:
you want to do exercises on balance ball/pads. Building up muscle memory is the most important, and obviously the best way is on a board itself, but being on balance pads/balls gives your muscles the twitch memory of having to balance/stabilize, making it easier once you're on a board again. Doing strength exercises (squats) while working those twitch muscles will help simulate the same stresses as when on a board while building up strength and conditioning.
Basically any leg exercise you would do in the gym will build up lower body strength. Don't be afraid to throw in some dead lifts as well, those will develop and strengthen your hamstrings and lower back, while squats will build your quads, glutes, and calves. But I agree with ttchad, squats and lunges are most beneficial
key note: If you want REAL progressive results, stay the f*** off the cardio machines. There are a list of reasons why doing cardio outside is WAY more beneficial. And quite frankly, Frozen is wrong. Walking at a constant rate will burn more calories than a spurratic run (i.e. slow jog...run...slow down again...run again), but unfortunately you're not a middle aged woman with excess body fat that just needs to lose calories, so that will not help so much (or so I assume)