The best overall training for FF, Law Enforcement, Military..ect hands down is crossfit. http://crossfit.com/
I wish I would have started going to a crossfit gym before I went throught the Academy,(a year ago) I would have been smokin most of the guys..Look at the site, and google to see if there's a gym around you to workout at.
Im 5'5" 125 lbs..so I know how hard it is to be in this profession and be that size.
Sorry to hear about your news, but my advice is read about crossfit, and even if you cant find a gym near you, there are many workouts you can do on your own. 6 months of training and you will be kickin ***! Good luck to you!
Remember two things: you can't start retirement saving too soon; and if you start piling up certificates and degrees, you can become administratively attractive then screw the short-career physical end by doing the brainiac stuff to allow the rest to do the phsyical work, for as long as you like.
Just stay away from the pastry shop by the old vollie bell!!