Hi Doc,
One option here is the one I and many others have taken. Gibor alluded to it, I think, but I am suggesting breaking things into smaller pieces. It may sound not as frum, but I don;t think it is:
Long before trying to focus on 'humbly serving G-d', make humility a goal in itself - G-d-service or no G-d-service. There is a lot on that in the 12 step literature, like in AA, the 12 and 12 on steps 3 and 7, and elsewhere. A drop of humility really makes life less heavy, less tense, and a lot more fun for ourselves and for all those around us.
But even before that, i have to do something first:
Accept G-d's Will for me. And that has nothing directly to do with being frum. It's more about accepting the Torah - not yet the mitzvos, for actually, the majority of the Torah is not about mitzvos!
"Istakloh b'oraiso ubara almoh" means that for everything that happens in this world, in your life, there is a remez in the Torah. It's somewhere in there, as the GR"A and many others spend time explaining. How fat you are, how much money you have, make or don't make today is in there. How much money you have made till now, how your wife has treated you, whether you are married yet, how many children you have, you health, your wife's health, how the guy next to you drives this evening on his way to work, how his wife treats him that affects his mood and the way he will drive and the traffic jam it will cause affecting the lives of 2-3 thousand people w/you on the freeway this morning, how your hair looks if you have any, what rebbi and teachers your kids have and their moods today, and whether your boss is nice to you or not, etc, etc... today and every day forever...they are all tailored expressions of His Will for you.
I'd estimate there are 10,000 variables at the very least (maybe more like 100,000) and are the ways His Will specified for you will be expressed today. Now, how many mitzvos and halachos really come your way on a given day? 200-300 or so, at most?
With mitzvos, we frummies consider whether to accept His will, meaning whether to keep it - to do it - or not to do it. But at it's core, the 3rd step is not about that! Its is about accepting His Will for us. Not doing it, but just accepting that His Will is at work through the day throughout our lives, on all those myriad factors that make up our real lives: How we look, what happens to us, what we've got, have't got, etc...
Most of those things we see and know, but do not accept. This stuff is very basic and deceptively obvious. But as Mesilas Yeshorim points out, to the extent that it is obvious, people ignore it. There are amputees who know they are missing a leg, wear a prosthesis to hide it, and cry over their disfigured body every now and then - they may know they are amputees, but do not accept it yet. So they suffer terribly...maybe forever.
But there are many amputees who readily admit it. If they ever see a person who has recently lost their leg, these are the folks who will go over and say, "Hi, I'm Sammy, and I'm an amputee, too. It's OK. My life is just fine," and start up a candid discussion with the unaccepting one. It changes lives. All because they accept the facts about themselves.
But to do that, an amputee needs to lose the shame of having a leg missing. Some people (you will see it here) deal with it by shunning labels and say, "I wouldn't ever say 'I am an amputee' - because that is not what I am at my core." Gibberish. Being an amputee does not define me as a person. It's just a true thing about me. And also, it is not disgusting, either - even if you, him, and most people in this room might think that it is! I do not accept that, and know that it is not disgusting. Acceptance means coming to peace with it, with the facts.
And BTW, it's the same with 'addict'. I am an addict. A sex and lust addict. If i know it but do not accept it, then I will be trying to run from myself. Here on GYE we call that, "struggling". And I will fail. But if I accept it, then I am accepting G-d's Will for me. I am a Jew, a father, a husband, a xyz shul member, am short, fat, a kolel man, a sex addict, and lots of other things. Now that I truly and fully accept it - I can start to learn what addicts do to live right. But not before.
Sorry I strayed to addiction. My main point is that before accepting avodas Hashem, how about spending a few months just trying to accept the Will of Hashem for you? Your life circumstances, your limitations, your people. As they all are. Just for a while. Not knowing them, but accepting them.
If you are already doing that, I contend that you would not be falling. Lust would not find a foothold in your mind. You'd be too busy living life rather than trying to outsmart it. I am not accusing you of being a bad guy - just normal.
It may be the first way you will really start to learn about G-d in your life. Works for me...
Just a thought to consider. Not changing from davening or anything else, but just a change on focus for a good while.
And a few months after that you can start to talk about focusing on serving G-d humbly, and actually get some traction there. And pray for me please.