First, if you haven't already go check out AOPA's Let's Go Flying site - specifically their page on how to pick a flight school/instructor. Some of the advice I'm going to give you is pretty much ripped right from them.
For my two cents, if you're going for a career move (even a part-time side job type career), you want to optimize your training path - you do not want to be like me where you're doing this whole aviation thing "just for kicks" and can be be a perpetual student pilot taking as long as you want to get each rating!
Generally speaking this means you want to follow the "traditional" path of certificates and ratings in your chosen aircraft category and class. For Airplanes that would be Private Pilot, Instrument Rating, Commercial Pilot, and CFI.
You probably don't want to "detour" to ratings like Sport Pilot (unless you want to become a sport pilot instructor and don't intend to ever become a "regular" CFI, in which case this path lets you skip the instrument and commercial ratings).
The private->Instrument->Commercial->CFI path is "typical" in my experience, and it generally seems to make sense because the skills you use in each phase naturally build on each other and will help you with the more difficult tasks the next rating will demand.
It's probably also worth spending a little time with the Part 61 requirements for each certificate and rating you intend to pick up and planning ahead -- for example, if you can economize by making sure your instrument rating cross-country flight time requirements also satisfy some or all of the requirements for the Commercial rating you can avoid having to do basically the same flying twice.
As far as where you do your training, a lot of that depends on your personal situation (funding, schedule and personality). The general rule here is "the more you fly the faster the training goes". I was a weekend warrior for most of my private training, and between weather delays and extended gaps between lessons it took me a LONG time to get that first ticket - the instrument rating may end up taking just as long!
If you're a good student, can take a substantial block of vacation, and have the money to throw at your training an accelerated/immersive program is often the most cost-effective and shortest route to a given certificate or rating: You are effectively becoming a full-time flight student, flying and studying every day, and when you eat, breathe, and sleep aviation you generally pick things up a lot quicker.
As an added advantage these are often Part 141 programs, which reduces the hour requirements for the certificates and ratings (but even if the training is conducted under Part 61 you're still at an advantage because of the immersive nature of the program).
If becoming a full-time student is not an option for you a structured Part 141 program may still be: Some Part 141 schools have "weekend warrior" programs that follow the same syllabus, and have the same benefit of reducing the hour requirements. The drawback is they're not as "immersive", so information may not sink in as quickly and skills will probably take longer to develop - you'll take longer (and probably spend more money) as a weekend student than you would as a full-time student.
The last option is "regular" Part 61 training, which is what most of the folks I know with day jobs they can't escape from do. This is certainly the most flexible option as you're basically training on your own schedule and program. Good instructors will almost universally still be working from some kind of syllabus to keep your training on-track and moving forward, but there's more freedom to jump around and change up the order of lessons, which is nice if you're getting stuck, or bored, or need to really work on a specific maneuver/concept for a while.
The downside is the same as I already mentioned for "weekend warrior" 141 training: the time between lessons really puts a hurting on your mechanical skill development and knowledge retention, and you'll probably wind up taking longer to finish your training.
There is however no reason you couldn't finish up a Part 61 training program right around the bare minimums for each certificate/rating, assuming you fly frequently and don't hit too many personal stumbling blocks along the way.