I've also had trouble understanding this point all my life. There are many answers offered and the one that made sense to me is the one offered by chassidut, and therefore I'd like to bring it now. I hope to see other answers as well.
The concept of humility seems almost impossible to embrace, yet we are told that "For it is exceedingly near to you, in your mouth and in your heart, to do" (Devarim 30:14), which the Alter Rebbe in Tanya explains means that it is supposed to be easy and natural for a Jew to be able to keep all mitzvot and Torah precepts, including being humble. If we are finding it hard, we have either misunderstood ourselves or misunderstood what humility means.
I once heard in a shiur that one is not supposed to compromise in marriage, despite common wisdom. Then he proceeded to give a story about a couple who, for many decades, whenever they would fly on a plane, the husband would sit by the window and wife by the aisle. At some point, they realised that each spouse thought the other preferred that seat, so they were offering it to them, but the truth is that it was the other way around! One figured that he likes the aisle, but he will gladly give it to her and sit by the window. She figured that the window was best so she gladly gave it to her husband. This is not about compromise at all, neither were compromising, in fact, they never realised because they were actually both getting what they really wanted - making their spouse happy.
This is the essence of bittul, or humility. There is a famous pasuk in Shir HaShirim - I am for my beloved and my beloved is for me. This is a chassidic answer, which means it's all about relationships - relationships are the most Godly aspect of creation, so how does God want us to structure our relationships?
What He wants from us is 2 things. 1 is that we should have our own self identity, which really boils down to having a personality and things that we want and like, that makes us unique (Ratzon is the highest sefira, and therefore the most fundamental). Then, He wants us to become people whose greatest pleasure and enjoyment in life is serving others. He doesn't want us to have no other wants, and there is a reason for that, which we will get to in a moment, but He does want our greatest, highest goal and ambition in life to be "for our beloveds", not for ourselves.
A quick detour to discussing the tree of knowledge of good and evil. This has been explained in many ways and the chassidic explanation is like this. It is a tree of da'at (which is the spiritual ability to internalise knowledge, and leads to self identity and self consciousness), and it is both good and bad. Why is it good? It is good because it means that we can actually be separate individuals and therefore it enables genuinely Godly relationships. It is bad because it can make us into selfish individuals who only are "for myself".
So back to the couple we discussed above. If either of them were completely selfless, then there wouldn't been any room for a relationship. The husband, desperate to give something to his wife that she wants, would find she wants nothing and therefore not be able to find anyone there to love and be for, and visa versa. However, because they are both individuals, they both do have something with which to serve each other and be served by. When the husband thought his wife would prefer the aisle, he got to do something very Godly, and let her have it. He got to do so at his own expense, which was great, he absolutely lives for her and there is no greater pleasure in the world than making her happy and giving her what she wants - serving her. The fact that he had to not get what he wanted was not a compromise, in fact it enhanced his service for her, he got to do something particularly grand on her behalf, at his own expense. When he found out that she actually preferred the window seat, you understand the mixed feelings - all very Godly - where he felt sad that he hadn't actually been serving her, but happy that he found out what makes her happy and can actually give that to her, but also a little sad that he now is going to be giving less altruistically to her because now it's going to be easy, as he will actually be getting what he wants.
That's ultimately what this world is all about and why Hashem started this whole mess. The highest spiritual plane is the plane of Atzilut, which is the world of "there's nothing but you". Our souls are all rooted there. However, when it truly is that we are all over the moon to serve others and never think about ourselves, there are a few questions that can be asked that taint it. Firstly, what is there to serve others, when everyone is selfless? Secondly, what is the greatness of serving others if it is so natural and Godly to a soul, and there's no resistance or challenge in it?
So we are sent to the lowest world, the world of Asiya, a world where we are predominantly out for ourselves. We feel our own needs much stronger than the needs of others and our natural instinct is to put them first, no matter the cost. If there's any time and energy left over, then we might consider serving someone else. Hashem invites us, step by step, to rise through the worlds. First the world of Yetzira, where we are able to view the needs of others as just as important as our own. The world of compromising. Then we step up to the world of Beriya, where we actually become more interested in the needs of others than our own needs.
After we have stepped through all this, then we can enter the world of Atzilut again, where all we see is our beloved, not ourselves. The questions that were asked before we left have all fallen away, and along the way we have become dynamic, wonderful people, who have something for our beloveds' to serve ("my beloved is for me" remember!).
The first step in all this is to realise that it is better to be needed than it is to be needy. This is what will shake us out of our Asiya-dik stupor and realise that there is indeed a great nobility and pleasure in serving others. When we truly start to see the greatness in the fact that we are needed, and allow others to also respond to our need, we are well on our way back to Atzilut, with a strong momentum that lasts and doesn't require constant "inspiration" and "chizuk" to keep us going. One thing we realise is that there's nothing wrong with taking pleasure in being altruistic either. If my main pleasure in life is "being for my beloved", then that's about as Godly as it gets. And if we are worried that you will be challenged, when we get back to Atzilut, that we only did it for the pleasure - don't worry. Much of the time, in this cold, dark world, we don't feel the pleasure or the connection. That's often just a gift from Hashem in the moment, to make us remember what the right path is. We will respond to the needs of others under a lot of heroic challenge in life, leave that up to Hashem.
At least now we understand what it means to be humble, why it isn't "across the sea" or "in the heavens" that we should have to go and get it (Devarim 30:12-13). It's doable, easy (yet challenging) and makes sense. Only one who truly grasps this concept will understand what the Rambam you quoted is saying: in order to serve others effectively, one has to first look after one's self. Primarily, so that one has the energy and wherewithal to rise to the immensely important, holy task of serving others, but also because they need to give to you too. If you are nothing, they have nobody to give to, and you will deny Hashem what He created the whole world for - true intimacy and oneness between each other.