IMO, it doesn't matter whether you start with a Part 91, 135, or 121 job. Get the ATP and Class 1 medical cert in any case, so you're ready when the call comes for the "big" job.With your military experience, currency is more important than the type of airplane or operation.
I'd go for the job that pays more. If it goes away before you get the job you really want, you will still have the time/experience as well as the extra $$ in your savings account. The regionals will likely be hiring constantly, and the majors will likely be hiring significant numbers starting next spring, latest.