There is a story (I don't recall the details or the source) where a habitual sinner - if I recall correctly, a thief - asked his Rabbi for where to start in doing teshuvah. The Rabbi tells him to accept on himself to always tell the truth (which is actually abstaining from violating the negative commandment לא תשקרו, not to lie). This ended up working, because the next time the guy was tempted to steal, he realized that he wouldn't be able to lie his way out of it.
Another story has a Jewish soldier in WWI - pretty well assimilated, but having a warm relationship with his community's Rabbi - being advised to keep the mitzvah (again, a negative commandment) of abstaining from non-kosher wine, with the idea that this would help him maintain some concept of the differentiation between Jews and non-Jews. (The story goes on to tell how his careful observance of this saved his life.)
So there is a strong case to be made for starting with commitment to a negative commandment first.
On the other hand, the Chinuch (which I quoted in an answer to a different question, here) calls the mitzvah of tefillin, a positive commandment, "a great fundamental principle and a major protection against sin, and a strong ladder by which to ascend and enter into the service of the Creator." Historically, the Semag (R' Moshe of Coucy) indeed devoted a great deal of effort to getting religiously-lax Jews to start putting on tefillin (with this idea in mind), and in our generation the Lubavitcher Rebbe zt"ll did the same.
All of which, then, goes to support Isaac's and Shalom's points: there is probably no one-size-fits-all answer.