I don't have sources, but I can answer from personal experience. All of the mitzvot of Shabbat are important, but the ones they should start with are the ones that will make the biggest impact. Those are:
Those that are easy for them to do, because early successes make the whole task seem less daunting.
Those that involve a fundamental change that they can actually do now, because these changes give them something big to point to to say both (a) I accomplished something and (b) and if I could do that then surely I can do (whatever the next one is).
What exactly these are will vary from person to person. In my case, for example, it was not too difficult to change my work schedule so that I could be home before candle-lighting time on Friday -- an example of #2, really setting aside my employment for Shabbat. On the other hand, when I began to observe Shabbat I lived several miles from the nearest synagogue, so not driving wasn't going to happen at that time. (I needed my Shabbat community more than I needed to not kindle that particular flame.) Later -- much later -- I moved and solved that problem, but I couldn't have done it at the beginning. For others it could be the reverse -- maybe you already live near shuls but you're going to need to find a new job to fix the work schedule. Work was in category 1 for me and driving in category 2; for you it could be the reverse.
Further, don't neglect the "do"s and the "small" things. People new to Shabbat tend, in my experience, to think of it mostly as the "thou shalt nots". It can take a while to get into the head-space of Shabbat being a welcome separation from ordinary time instead of a day of restrictions. So make sure to take on the positive things! Festive meals with family/friends make a big difference. Join a torah-study group on Shabbat morning or an afternoon class on something that interests you. Do things that help you relax and enjoy the day (without introducing melachot -- e.g. some people relax by gardening, but instead try walks in the park where you can appreciate others' flowers instead).
Shabbat is a process. As soon as you're somewhat comfortable with what you're already doing, try to take on the next thing, whatever it is. When choosing, in addition to the two factors I mentioned, try to prefer d'oraita obligations -- the d'rabbanans are important too, but the divine punishment for violating d'oraita prohibitions is more severe, so start there. But if there's some d'rabbanan thing that makes you say "oh hey, I could do that easily enough" -- then do it. The more you can do and actually integrate into your weekly routine, the easier it will be to do the others.