There really is no conflict between the Rambam and Sha'arei Teshuva. People tend to overlook a key paragraph in the beginning of Sha'arei Teshuva:
And behold that there are many levels of repentance. It is true that you will find forgiveness for any repentance. However the soul will only find complete purification - to be as if the iniquities never had been - when a person purifies his heart and prepares his spirit, as will be explained. And so is it written (Psalms 32:2), "Happy is the man whom the Lord does not hold guilty, and in whose spirit there is no deceit." And it is like the matter of a garment that needs washing: For a little washing will be effective to remove its soiling. However, it will [only] whiten according to the amount of washing. And so is it written there (Psalms 51:4), "Wash me thoroughly of my iniquity.
In other words, the immediate and basic act of repentance does remove the sin, however, more repentance is needed to completely remove all its effects. This is the regret, confession, and resolve. (As an aside, it is not clear that the Sha'arei Teshuva requires verbal confession.)
I saw in a sefer about the Chofetz Chaim a rabbi who was going to South Africa asked him what he could tell the people in the name of the Chofetz Chaim. He replied: "Tell them teshuva is a simple matter, regret over the past and resolve for the future, but the yetzer hara makes it look difficult."
And finally, there is a much shorter essay by Rabbeinu Yonah called Yesod Hateshuva that is printed in many Rosh Hashana Machzorim that gives a more basic guide for the person on the day he chooses to do teshuva. [In that essay he says not to think about the past. This would seem to contradict much of Sha'arei Teshuva, but I think the difference is that to immediately break one's habit, it is better to ignore the past. Later, one can do a more thorough teshuva when the actual habit is broken.]